visual walkthrough
Reverse Linked List II
Reversal of a sub-range with correct reconnection.
The idea
Only a slice of the list is reversed, so the nodes around it must be reconnected afterwards. Keep a pointer to the node just before the slice.
Then pull each later node of the slice to the front, one at a time. After right − left moves the slice is reversed and still connected at both ends.
Complexity
| approach | time | space |
|---|---|---|
| Copy values and write back | O(n) | O(right − left) |
| Move nodes to the front | O(n) | O(1) |