# A python solution O(n) time, O(1) space

• ``````# Splits in place a list in two halves, the first half is >= in size than the second.
# @return A tuple containing the heads of the two halves
while fast and fast.next:
slow = slow.next
fast = fast.next
fast = fast.next

middle = slow.next
slow.next = None

# Reverses in place a list.
# @return Returns the head of the new reversed list

last = None

while currentNode:
nextNode = currentNode.next
currentNode.next = last
last = currentNode
currentNode = nextNode

return last

# Merges in place two lists
# @return The newly merged list.
def _mergeLists(a, b):

tail = a

a = a.next
while b:
tail.next = b
tail = tail.next
b = b.next
if a:
a, b = b, a

class Solution:

# @return nothing

return

b = _reverseList(b)

• A concise version

``````def reorderList(self, head):
return

# find the mid point
while fast and fast.next:
slow = slow.next
fast = fast.next.next

# reverse the second half in-place
pre, node = None, slow
while node:
pre, node.next, node = node, pre, node.next

# Merge in-place; Note : the last node of "first" and "second" are the same
while second.next:
first.next, first = second, first.next
second.next, second = first, second.next
return ``````

• I came up with a very similar code, but in the second while loop I wrote `pre, node, node.next = node, node.next, pre` instead of `pre, node.next, node = node, pre, node.next`. Why does switching the order of assignment matter here? I thought Python evaluated the entire right side before doing any assignment at all?

• You are right that the right hand side would be evaluated first. But then it will assign these value/objects to those on the left hand side one by one. In your code, the original node.next will be assign to the new `node` first, and then the original pre will be assigned to the NEW `node.next` since `node` has already been assigned to a new object.

• @cmc Elegant Solution :astonished:

• @cmc

Note : the last node of "first" and "second" are the same

The note is valid when the linked list has "odd" number of nodes, but not true when there are even number of nodes.

• A concise version

``````def reorderList(self, head):
return

# find the mid point
while fast and fast.next:
slow = slow.next
fast = fast.next.next

# reverse the second half in-place
pre, node = None, slow
while node:
pre, node.next, node = node, pre, node.next

# Merge in-place; Note : the last node of "first" and "second" are the same
while second.next:
first.next, first = second, first.next
second.next, second = first, second.next
return
``````

this is a nice one

• first.next, first = second, first.next
second.next, second = first, second.next

I tried to change

``````first.next, first = second, first.next
second.next, second = first, second.next

to

next = first.next
first.next = second
first = next

next2 = second.next
second.next = first
second = next2

``````

• Upvoted. "the first half is >= in size than the second" is the key. These sort of off-by-one issue is the most confusing part in linked list questions.

• To clarify about the line `pre, node.next, node = node, pre, node.next`. We need to understand that the right hand side will be evaluated first before the assignment, and the left hand side will be assigned values one by one, from left to right. (First `pre`, and then `node` and the last `node.next`)

Let's say we have a linked list `1 -> 2 -> 3 -> 4 -> 5`. After we found the mid point, we have `pre = None, node = 3 -> 4 -> 5`

Before we run the multiple assignment:
`pre, node.next, node = node, pre, node.next`
the original values on the right hand side are: `node: 3 -> 4 -> 5, pre: None, node.next: 4 -> 5`

And then new `pre` will store the reference to original `node: 3->4->5`, and then `node.next` will refer to original `pre: None`, which means after these two assignments, we have new `pre: 3->None`.

At last we assign the original `node.next: 4->5` to new `node`, so the new `node` has `4->5`.

In the next iteration, the right hand side will have `node: 4->5, pre:3->None, node.next: 5->None`. Then the new `pre` is going to have `4->5` first, then the old `pre` will replace the tail of new `pre`, which makes it `4->3`. And new node would have `node: 5`.

Same as the next iteration.

So this line basically takes out each value in the linked list one by one in order, and then treat each one as tail and append it to the new one.

• any people knows that what's the meaning of second number of (128ms,0.28) in Accepted Solutions Runtime Distribution???

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