Reorder List
The problem
Rearrange a singly linked list in place so its nodes alternate from the front and back: first, last, second, second-last, and so on. Keep node values unchanged.
Example
1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3
Need a hint?
Split, reverse, then weave.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Find the midpoint with slow and fast pointers. Disconnect the second half and reverse it. Alternately splice one node from each half, saving next pointers before rewiring. The first half may contain one extra node for odd lengths. Disconnecting the halves prevents cycles.
Complexity
O(n) time and O(1) extra space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.