LeetCode----Partition List

LeetCode----Partition List

Partition List

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

分析：

實現鏈表的分割，類似於快排中的分割。

我的方法非常簡單，遍歷鏈表，建立兩個鏈表，s表示小鏈表，裡面的元素值均小於給定元素x；b表示大鏈表，裡面的元素均大於等於給定元素x。

遍歷時，對每個節點進行判斷，然後放入對應的s或b的鏈表，最後再將s和b鏈表進行連接返回。

代碼：

class Solution(object):
    def partition(self, head, x):
        
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        
        p = head
        ss = s = ListNode(-1)  # ss record the start of smaller linkedlist, s record the node in smaller linkedlist
        sb = b = ListNode(-1)  # sb record the start of bigger linkedlist, b record the node in bigger linkedlist
        while p:
            if p.val >= x:
                b.next = p
                p = p.next
                b = b.next
                b.next = None
            else:
                s.next = p
                p = p.next
                s = s.next
                s.next = None
        s.next = sb.next
        return ss.next