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
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?
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~
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"..
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.
My accepted solution is much complicated than this one.
def partition(self, head, x): dummy = ListNode(0) dummy.next = head pre, cur, pivot = dummy, head, dummy while cur: if cur.val < x: if pivot.next != cur: old_pivot_next = pivot.next pre.next = cur.next pivot.next = cur pivot = pivot.next old_cur_next = cur.next cur.next = old_pivot_next cur = old_cur_next else: pivot.next = cur pivot = pivot.next pre = cur cur = cur.next else: pre = cur cur = cur.next return dummy.next
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.