Reverse a linked list in place
[1,2,3,4,5] becomes [1,5,2,4,3]
The naive approach is to continuously reverse the tail. A more interesting approach is to notice that we alternate two elements:
- One that come from the first part of the list
- One that come from the second part of the list
Therefore we can:
- Find the mid of the list using fast/slow pointer
- Reverse the second part of the list
- Merge the first part and the second part taking one element from each