Given the head of a singly linked list L0 -> L1 -> ... -> Ln, reorder its nodes in place into L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ..., alternately taking one node from the front and one from the back. Return the head. Move the nodes themselves; do not just rewrite the values.
Examples
Input: head = 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3
Input: head = 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
Constraints
0 <= number of nodes <= 10**4- Target: O(n) time, O(1) extra space
Goals
- Combine splitting, reversing and interleaving into one algorithm
- Keep every operation in place with O(1) extra space