Similar as partition procedure in quick sort

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

    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.