Python concise solution with dummy nodes.


  • 17
    C
    def partition(self, head, x):
        h1 = l1 = ListNode(0)
        h2 = l2 = ListNode(0)
        while head:
            if head.val < x:
                l1.next = head
                l1 = l1.next
            else:
                l2.next = head
                l2 = l2.next
            head = head.next
        l2.next = None
        l1.next = h2.next
        return h1.next

  • 1
    Z

    Thank you for sharing!

    I am using exactly the same algorithm as you. I had problem because I was missing a statement like

    l2.next = None
    

    I don't think this should be necessary if the input is proper, but we have to add this to pass OJ?


  • 2
    C

    No, it's necessary. Suppose the list is 2->1, if you don't set l2.next = None, there will be a loop: 1->2 and 2 connects to 1 again. You can draw a figure to help you understand. Actually if you don't want to set l2.next = None, you can do like l2.next = ListNode(head.val), instead of l2.next = head in the "else" block. You can have a try~


  • 0
    Z

    Thank you for explaining!

    If the last node doesn't go to l2, l2 is not closed.

    But why the loop is infinite? I did not understand why you said "there will be a loop: 1->2 and 2 connects to 1 again"..


  • 1
    C

    After you do l1.next = h2.next, 1 will connect to 2, but in the original list you don't cut off the end of 2, so 2 is still connected to 1, so there will be a loop. If you set l2.next = None, then the final list will ony be 1->2. You can use a pen to figure it out.


Log in to reply
 

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