Accepted Python Code for O(n) time constant space


  • 0
    B
    class Solution:
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        if head==None:
            return
        vhead=ListNode(0)
        vhead.next=head
        end=head
        length=1
        while end.next!=None:
            end=end.next
            length+=1
        node=vhead
        for i in range(length):
            if node.next.val<x:
                node=node.next
            elif node.next!=end:
                temp=node.next.next
                end.next=node.next
                node.next.next=None
                end=node.next
                node.next=temp
        
        return vhead.next
    

    the trick is to handle when the node you are visiting now is the end of the list. This happens when the list is already partitioned to start with.

    if you see node.val<x, move on; if you see node.val>=x, throw it to the end of the current list. the order is automatically preserved.


Log in to reply
 

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