# Python concise solution with dummy nodes.

• ``````def partition(self, head, x):
h1 = l1 = ListNode(0)
h2 = l2 = ListNode(0)
l1 = l1.next
else:
l2 = l2.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)
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.