# 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
def _splitList(head):
fast = head
slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next
fast = fast.next
middle = slow.next
slow.next = None
return head, middle
# Reverses in place a list.
# @return Returns the head of the new reversed list
def _reverseList(head):
last = None
currentNode = head
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
head = a
a = a.next
while b:
tail.next = b
tail = tail.next
b = b.next
if a:
a, b = b, a
return head
class Solution:
# @param head, a ListNode
# @return nothing
def reorderList(self, head):
if not head or not head.next:
return
a, b = _splitList(head)
b = _reverseList(b)
head = _mergeLists(a, b)
A python solution O(n) time, O(1) space


A concise version
def reorderList(self, head): if not head: return # find the mid point slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # reverse the second half inplace pre, node = None, slow while node: pre, node.next, node = node, pre, node.next # Merge inplace; Note : the last node of "first" and "second" are the same first, second = head, pre 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 ofpre, 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 NEWnode.next
sincenode
has already been assigned to a new object.


@cmc said in A python solution O(n) time, O(1) space:
A concise version
def reorderList(self, head): if not head: return # find the mid point slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # reverse the second half inplace pre, node = None, slow while node: pre, node.next, node = node, pre, node.next # Merge inplace; Note : the last node of "first" and "second" are the same first, second = head, pre while second.next: first.next, first = second, first.next second.next, second = first, second.next return
this is a nice one

@cmc said in A python solution O(n) time, O(1) space:
first.next, first = second, first.next
second.next, second = first, second.nextI 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
it is more readable hahaha

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. (Firstpre
, and thennode
and the lastnode.next
)Let's say we have a linked list
1 > 2 > 3 > 4 > 5
. After we found the mid point, we havepre = 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 originalnode: 3>4>5
, and thennode.next
will refer to originalpre: None
, which means after these two assignments, we have newpre: 3>None
.At last we assign the original
node.next: 4>5
to newnode
, so the newnode
has4>5
.In the next iteration, the right hand side will have
node: 4>5, pre:3>None, node.next: 5>None
. Then the newpre
is going to have4>5
first, then the oldpre
will replace the tail of newpre
, which makes it4>3
. And new node would havenode: 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.