Python one pass, no extra memeory

  • 0
    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)
   = 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 =
                        last =
                        cur =
                    #move the "cur" to the end of "last" and update "last" and "cur"
                        tmp =
               = cur
               = tmp
                        last =
                        cur =
                    pre = cur
                    cur =

  • 0

    "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.