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.You should 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进行划分，得到划分之后的数组再组成链表。但是这种办法再应对链表比较长的时候就会存在问题。时间复杂度为O(n)(省略了系数), 空间复杂度为O(n)。另一种解法是我们可以直接该改变指针的方向，原地对链表进行分区。时间复杂度为O(n), 空间复杂度为O(1)。
图示解法
解决代码 1 # Definition for singly-linked list.
2 # class ListNode(object):
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution(object):
8 def partition(self, head, x):
9 """
10 :type head: ListNode
11 :type x: int
12 :rtype: ListNode
13 """
14 if not head or not head.next:
15 return head
16
17 res = ListNode(0) = one # 哨兵节点
18
19 while True:
20 while one.next and one.next.val < x: # 便利到下一个节点大于x市停止。
21 one = one.next
22 two = one.next # two节点从这个one的下一个节点来找到下一个节点小于x的系欸但使停止
23 while two.next and two.next.val >= x:
24 two = two.next
25
26 if not two.next or not one.next: # 如果两个节点任意一个为空，则表示没找到满足条件的节点。
27 return res.next
28 tem = two.next # 交换节点的指向为止，注意顺序不能改变，否则会出错。
29 two.next = tem.next
30 tem.next = one.next
31 one.next = tem