LeetCode解題之Partition List

原題

給定一個鏈表以及一個目標值，把小於該目標值的所有節點都移至鏈表的前端，大於等於目標值的節點移至鏈表的尾端，同時要保持這兩部分在原先鏈表中的相對位置。

注意點：

例子：

輸入: head = 1->4->3->2->5->2, x = 3

輸出: 1->2->2->4->3->5

解題思路

看成有一串珠子，有紅和藍兩種顏色，現在要把紅色和藍色分別集中到一起。可以遍歷每個珠子，如果是藍色就串在一條線上，紅色的串在另一條線上，最後把兩條線連起來就可以了。注意，在比較大的那串數中，最後的指針要置為None，因為那是排序後的最後一個節點。

AC源碼

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def to_list(self):
        return [self.val] + self.next.to_list() if self.next else [self.val]


class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)

        prev = dummy
        small_prev = small_dummy
        large_prev = large_dummy
        while prev.next:
            curr = prev.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            prev = prev.next
        large_prev.next = None
        small_prev.next = large_dummy.next
        return small_dummy.next


if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(4)
    n3 = ListNode(3)
    n4 = ListNode(2)
    n5 = ListNode(5)
    n6 = ListNode(2)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    n5.next = n6
    r = Solution().partition(n1, 3)
    assert r.to_list() == [1, 2, 2, 4, 3, 5]