visual walkthrough
Reverse Linked List
The single most important linked-list routine; do it iteratively and recursively.
The idea
Reversing a list doesn't mean moving nodes: every node stays where it is, and only its arrow turns around to point at the node before it.
Three pointers do it in one pass: prev (the reversed part), curr (the node being flipped) and next (saved first, so the rest of the list isn't lost).
Complexity
| approach | time | space |
|---|---|---|
| Copy and write back | O(n) | O(n) |
| Flip the arrows | O(n) | O(1) |