Python 9 lines with explanation


  • 0

    The idea is to create two list which store "less than" and "great of equal to" values and concatenate these two list together. Please see comment for details.

    class Solution(object):
        def partition(self, head, x):
            # create two linked list: lz and ge
            lzTail, geTail = lzHead, geHead = ListNode(0), ListNode(0)
    
            # split input into these two list
            while head:
                if head.val < x:
                    lzTail.next, lzTail = head, head
                else:
                    geTail.next, geTail = head, head
                head = head.next
    
            # concatenate the two list, make sure None is at the end of the list
            lzTail.next, geTail.next = geHead.next, None
    
            return lzHead.next
    
    

Log in to reply
 

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