Reorder List
Reorder a linked list from L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> ... in place.
Open on LeetCode ↗Intuition
The pattern alternates between the front of the list and the back, but a singly linked list cannot walk backwards — so build a half that already runs backwards. Find the middle, reverse the second half, then zip the two together. The step people skip is the cut: if you reverse without first setting slow.next = None, the reversed half is still linked into the first and you have quietly built a cycle. The other trap is in the merge, where you must save both next pointers before overwriting either.
Three textbook sub-routines composed: find the middle with slow/fast, reverse the second half, then zip the two halves together. Recognising a problem as a composition of known primitives — rather than one new algorithm — is what makes it tractable in an interview.
Approach
Find the middle with slow and fast pointers
Advance slow one node and fast two. When fast reaches the end, slow is at the middle. For even lengths this convention leaves the first half one node longer, which is exactly what the interleaving wants — the extra node ends up at the tail.
Reverse the second half
Cut the list at the middle by setting slow.next = None, then reverse the second half with the usual three-pointer loop. Now the second half is traversable from the original tail forwards, which is the access pattern the answer needs.
Merge alternately
Walk both halves, splicing one node from each in turn and saving the next pointers before overwriting them. Losing those references is the standard bug here. Because the first half is never shorter, the loop terminates cleanly with the second half exhausted first. All in place: O(n) time and O(1) space, versus the O(n) space of copying nodes into an array.
Solution & live demo
Common pitfalls
Not severing the first half
second = slow.next # reverse second...
second = slow.next slow.next = None
Without cutting, the first half's tail still points into the second half, which after reversal points back — creating a cycle. The merge loop then never terminates.
Starting fast at head instead of head.next
slow, fast = head, head
slow, fast = head, head.next
On an even-length list this leaves slow one node too far right, so the second half is shorter than the first and the interleave drops a node. Starting fast one ahead makes slow stop at the end of the first half for both parities.
Not saving both next pointers before relinking
first.next = second second.next = first.next
f, s = first.next, second.next first.next = second second.next = f
The first assignment overwrites first.next, so reading it afterwards yields the node just linked rather than the original successor — the list folds back on itself. Both successors must be captured before any pointer is written.
Edge cases
Already in the target order — return early.
The pattern is unchanged, so the merge is a no-op.
The reversed half still links back into the first, producing a cycle.
The middle node ends up last, which the slow/fast convention handles without a special case.