Implement the complete reorder in space.
Implementation details:
- Be careful with the middle: for even lengths, you want the first half to be one node longer
- After reversing,
secondpoints to the new head of the reversed half - In the merge phase, save
nextpointers before overwriting
This problem is a checkpoint.
If you can solve it cleanly, you've internalized the core linked list techniques. Test on: even length, odd length, two nodes, single node. Time: . Space: .