visual walkthrough
Odd Even Linked List
Partitions nodes into two chains in place.
The idea
Positions alternate odd, even, odd, even. So the odd nodes form a chain where each links two ahead, and so do the even nodes.
Build both chains at once by relinking, then hang the even chain off the end of the odd one.
Complexity
| approach | time | space |
|---|---|---|
| Copy into two arrays | O(n) | O(n) |
| Two chains | O(n) | O(1) |