LeetCode 86. 分隔链表（中）

典型的双指针问题，写出AC的代码之后，先对照题解找区别，再优化。

题目

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
# 考察知识点

双指针

核心思想

方法一、三指针 思想很简单
使用 p 指针进行遍历，small 指针跟踪保存较小的那一部分，big 指针跟踪保存较大的那一部分。
一次遍历结束之后，将 small 和 big 拼接返回即可，注意，由于可能出现数字0，所以判断 small 或 big 部分非空的条件不是 if samll.val 而是 small.val != None。

Python版本

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
29
30
31
32
33
34
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        pre_p, small, big = ListNode(None), ListNode(None), ListNode(None)
        big_dummy = ListNode(None)
        big_dummy.next = big
        small_dummy = ListNode(None)
        small_dummy.next = small
        pre_p.next = head
        p = head
        while p:
            if p.val < x:
                small.next = p
                small = small.next
            else:
                big.next = p
                big = big.next
            p = p.next
        
        small.next = None
        big.next = None
        small.next = big_dummy.next.next
        return small_dummy.next.next

Input = [[0,9,-6,0,-8,9,1,-2,5,-3,4,4,-5,0,9,-3,7,-2,7,-4,-7,-6,9,-9,4,-8,-3], [0,4,4,3,2,0,0,4,2,2], [1], [2,1], [1], [1, 4, 3, 2, 5, 2]]
Input1 = [-8, 4, 2, 2, 0, 3]
Answer = [[-9,0,9,-6,0,-8,9,1,-2,5,-3,4,4,-5,0,9,-3,7,-2,7,-4,-7,-6,9,4,-8,-3], [0,3,2,0,0,2,2,4,4,4], [1], [1, 2], [1], [1, 2, 2, 4, 3, 5]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        reslut = solution.partition(createList(Input[i]), Input1[i])
        printList(reslut)
        print(Answer[i])

时间复杂度：\(O(n)\)，循环一遍。
空间复杂度：\(O(1)\)，只是用了常数级别的额外空间，几个指针。
执行用时 :36 ms, 在所有 Python3 提交中击败了80.22%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.88%的用户

浪费时间改出来一个简洁度、效率都不好的版本

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
29
30
31
32
33
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head:  return None
        p = head
        # 先确定第一个节点的归属
        if p.val < x:  # 加入small
            small = p
            big = ListNode(None)
        else:  # 加入big
            small = ListNode(None)
            big = p
        big_dummy = ListNode(None)  # small部分节点
        big_dummy.next = big
        small_dummy = ListNode(None)  # big部分节点
        small_dummy.next = small
        p = p.next  # 从第二个节点开始遍历
        while p:
            if p.val < x:
                small.next = p
                small = small.next
            else:
                big.next = p
                big = big.next
            p = p.next

        big.next = None
        while small_dummy.next and small_dummy.val == None:  # 这里要注意防止0被误删除
            small_dummy = small_dummy.next
        while big_dummy.next and big_dummy.val == None:
            big_dummy = big_dummy.next
        small.next = big_dummy if big_dummy.val!=None else None
        return small_dummy if small_dummy.val!=None else big_dummy  # 注意判断条件是small_dummy.val!=None，small_dummy.val可能是0。

时间复杂度：\(O(n)\)，循环一遍。
空间复杂度：\(O(1)\)，只是用了常数级别的额外空间，几个指针。
执行用时 :52 ms, 在所有 Python3 提交中击败了21.76%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.88%的用户

  • LeetCode官方答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def partition(self, head, x):
        before = before_head = ListNode(0)  # 申明一次，使用两次。
        after = after_head = ListNode(0)

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_head.next

        return before_head.next