The tell: Interleave the list with its own reverse, in place.
How you get there
1Find the midpoint with fast and slow pointers.
2Reverse the second half.
3Weave the two halves together, alternating nodes.
Solution
Python
def reorder_list(head) -> None:
if not head or not head.next:
return
slow, fast = head, head.next # midpoint
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second, slow.next = slow.next, None # split
prev = None
while second: # reverse second half
second.next, prev, second = prev, second, second.next
first, second = head, prev # weave
while second:
first.next, second.next, first, second = second, first.next, first.next, second.next
Time
O(n)
Space
O(1)
What goes wrong
Forgetting to cut the list at the midpoint creates a cycle when the halves are woven.