Python concise solution with dummy nodes.

  • 19
    def partition(self, head, x):
        h1 = l1 = ListNode(0)
        h2 = l2 = ListNode(0)
        while head:
            if head.val < x:
       = head
                l1 =
       = head
                l2 =
            head = = None =

  • 1

    Thank you for sharing!

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

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

  • 2

    No, it's necessary. Suppose the list is 2->1, if you don't set = 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 = None, you can do like = ListNode(head.val), instead of = head in the "else" block. You can have a try~

  • 0

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

  • 2

    After you do =, 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 = 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.