Similar as partition procedure in quick sort


  • 0
    J
    class Solution:
        # @param head, a ListNode
        # @param x, an integer
        # @return a ListNode
        def partition(self, head, x):
            new_head = ListNode(0)
            new_head.next = head
            pointer_slow = new_head
            pointer_fast = new_head
            while pointer_fast.next:
                if pointer_fast.next.val < x:
                    if pointer_slow == pointer_fast:
                        pointer_fast = pointer_fast.next
                        pointer_slow = pointer_slow.next
                        continue
    
                    # insert after pointer slow
                    tmp_node = pointer_slow.next
                    pointer_slow.next = pointer_fast.next
                    pointer_fast.next = pointer_fast.next.next
                    pointer_slow.next.next = tmp_node
                    # update pointer position
                    pointer_slow = pointer_slow.next
                else:
                    pointer_fast = pointer_fast.next
    
            return new_head.next
    

    We need two pointer here: faster and slow. Faster pointer is used to loop over the linked list, at the same time slow pointer is used to point out the last node whose value is smaller than x. If the faster pointer encounter a node whose value is smaller than x, then insert the node in slow pointer's next.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.