Partition List 解题报告（Python）
题目地址：https://leetcode.com/problems/partition-list/description/
题目描述：
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
Youshould preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
题目大意
要把一个单链表中，小于某个数字的所有节点放到前面，其余的位置都不要变化。
解题方法
乍一看，感觉原地做这些操作很难。但是，我们换个思路就感觉很简单了。
做链表的题，不要省指针。
用两个新指针，分别记录比x值小的和比x值大的，遍历原来的链表的时候根据值的大小拼接到对应的链表后面。
最后再把两个链表拼接到一起就行了。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
small = ListNode(0)
large = ListNode(0)
small_root, large_root = small, large
while head:
if head.val < x:
small.next = head
small = small.next
else:
large.next = head
large = large.next
temp = head.next
head.next = None
head = temp
small.next = large_root.next
return small_root.next
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发