visual walkthrough
Swap Nodes in Pairs
Local pointer rewiring in pairs.
The idea
Swapping two nodes means changing three arrows: the one into the pair, the one between them, and the one out of the pair.
Change them in the right order (first point a past b) and nothing is ever lost. A dummy head gives the first pair a "prev" too.
Complexity
| approach | time | space |
|---|---|---|
| Array of nodes | O(n) | O(n) |
| Relink each pair | O(n) | O(1) |