Problem Statement
Reorder List
You have a singly linked list. A linked list is a chain of boxes called nodes, where each node holds a value and a pointer (an arrow) to the next node. "Singly" means each box only points forward, never back. The list looks like L0, then L1, then L2, all the way to Ln. Your job is to rewrite the arrows so the order becomes L0, Ln, L1, Ln-1, L2, Ln-2, and so on. In plain words: take the first node, then the last, then the second, then the second to last, weaving the front and the back together. You must do this in place, meaning you rearrange the arrows themselves and never copy values into a new structure. There is a clean trick for this: combine three small linked list moves. (1) Find the middle of the list. (2) Reverse the back half. (3) Stitch the two halves together one node at a time.
Signals to notice
Brute force first
Convert to array, reorder by index, rebuild — O(n) space.
The key insight
Find middle (slow/fast) → reverse second half → interleave both halves. O(n) time, O(1) space.
Trace it on list = 1→2→3→4→5
Find middle: slow=1,fast=1 → slow=2,fast=3 → slow=3,fast=5; fast.next=null so stop. slow at node 3. Split: second=slow.next=4; set slow.next=None. Now first half 1→2→3, tail 4→5. Reverse second half (4→5): walk nodes flipping links → prev=5→4. second head = 5. Merge start: first=1, second=5. Save tmp1=2, tmp2=4. Link 1→5→2. Advance first=2, second=4. Merge: first=2, second=4. Save tmp1=3, tmp2=null. Link 2→4→3. Advance first=3, second=null. second is null → loop ends. List is 1→5→2→4→3. Return (in-place): 1→5→2→4→3.
What must stay true
The reordered list alternates between first-half (forward) and second-half (reversed). Three operations achieve this without extra space.
Shape of the loop
slow, fast = head, head
while fast.next and fast.next.next: slow=slow.next; fast=fast.next.next
second = reverse(slow.next); slow.next = None
first = head
while second:
first.next, second.next, first, second = second, first.next, first.next, second.nextPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not splitting the list properly — set middle.next = null to disconnect before reversing.