DSA problem
Reorder List
You are given the head of a singly linked list. The list can be conceptually represented as L0 -> L1 -> ... -> Ln-1 -> Ln. Reorder it into the interleaved form L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ..., where you alternately take a node from the front and a node from the back. You may not modify the values stored in the nodes; only the node pointers themselves may change.
A brute-force solution would store the nodes in an array for O(1) random access by index and then re-link them, but that requires O(n) extra space. The optimal solution achieves the reordering in O(1) extra space using only pointer manipulation.
The reordering combines three classic linked-list techniques. First, find the middle node using the slow/fast pointer method. Second, reverse the second half of the list in place. Third, merge the first half and the reversed second half by alternating nodes from each.
The intuition is that after splitting and reversing, the second half traversed forward gives exactly the back-to-front order we want (Ln, Ln-1, ...). Merging it node-by-node with the first half produces the alternating pattern directly. Each of the three phases is linear and uses constant space, so the overall algorithm is O(n) time and O(1) space.
Examples
head = [1,2,3,4][1,4,2,3]head = [1,2,3,4,5][1,5,2,4,3]head = [1,2][1,2]Constraints
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.