visual walkthrough
Reorder List
Chains three core routines together; a great consolidation problem.
The idea
The order L0, Ln, L1, Ln−1, … needs the back of the list, which a singly linked list can only reach by walking.
Split it in half, reverse the back half so its end comes first, then weave the two halves together node by node.
Complexity
| approach | time | space |
|---|---|---|
| Array of nodes | O(n) | O(n) |
| Middle, reverse, weave | O(n) | O(1) |