Python one pass, no extra memeory


  • 0
    P
    class Solution:
        # @param {ListNode} head
        # @param {integer} x
        # @return {ListNode}
        def partition(self, head, x):
            #create a new head to make the iteration easier
            newHead =ListNode(-1)
            newHead.next = head
            cur = head
            #"pre" is the node ahead of "cur"
            pre = newHead
            #"last" is the last node that smaller than x so far
            last = newHead
            while cur:
                if cur.val < x:
                    #if "pre" is "last", it means we haven't done any partition yet, so we do not need to do anything
                    if pre == last:
                        pre = pre.next
                        last = last.next
                        cur = cur.next
                    #move the "cur" to the end of "last" and update "last" and "cur"
                    else:
                        tmp = last.next
                        pre.next = cur.next
                        last.next = cur
                        cur.next = tmp
                        last = last.next
                        cur = pre.next
                else:
                    pre = cur
                    cur = cur.next
            return newHead.next

  • 0
    T

    "no extra memory" VS "create a new head"... so you are using extra memory, just constant == O(1).


Log in to reply
 

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