Given the head of a list L0 -> L1 -> ... -> Ln, reorder it to L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... — first, last, second, second-to-last, and so on. Rearrange the existing nodes (no value copying) and return the head. The classic asks for this purely in place; returning the head just lets the runner see your work.
Examples
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Example 3:
Input: head = [1]
Output: [1]
Example 4:
Input: head = [1,2]
Output: [1,2]
Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values. Dummy heads: a node in front of the list so the first element stops being a special case. Two pointers on a list — one ahead of the other, or one moving twice as fast.
How to think about it
1. Split, Reverse, Weave Optimal
Intuition
The target order takes from the front and the back alternately, and a singly linked list cannot walk backwards — so make the back half walk forwards instead by reversing it. Three techniques in sequence, which is why this problem gets asked: find the middle with slow and fast pointers, reverse the second half, then interleave. Cutting the first half's tail before weaving is the step everyone forgets, and without it the two halves stay joined and the weave loops.
Algorithm
1. Find the middle with slow and fast pointers. 2. Cut there, so the first half ends cleanly. 3. Reverse the second half. 4. Weave the two halves, taking one node from each in turn.