Using a pointer to record last node that is smaller than x


  • 0
    L
    class Solution:
        # @param {ListNode} head
        # @param {integer} x
        # @return {ListNode}
        def partition(self, head, x):
            current = head
            prev = ListNode(-1)
            prev.next = head
            #Mark the last node that is smaller than x
            last = head = prev
            while current:
                if current.val >= x:
                #Move prev and current forward if current value is not smaller than x, last remains the same
                    prev = current
                    current = current.next
                else:
                    if prev == last:
                        #Move last, prev and current forward 
                        prev = last = current
                        current = current.next
                    else:
                        #Put the current node between last and last.next
                        prev.next = current.next
                        current.next = last.next
                        last.next = current
                        #Update last and current, prev remains the same
                        last = current
                        current = prev.next
            return head.next

Log in to reply
 

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