Reorder List
MediumLinked List
You are given head, the first node of a singly linked list whose nodes are, in order, L0 -> L1 -> ... -> Ln-1 -> Ln.
Rearrange the nodes in place so the list becomes:
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
That is, alternate between the front and the back of the original list, working inward. You must relink the existing nodes; do not change any node's value. The function returns nothing: the tests read the list starting from the original head after your function runs.
Example 1
- Input:
- head = [1,2,3,4,5,6]
- Output:
- [1,6,2,5,3,4]
- Explanation
- Take the first node, then the last, then the second, then the second-to-last, and so on: 1, 6, 2, 5, 3, 4.
Example 2
- Input:
- head = [10,20,30,40,50,60,70]
- Output:
- [10,70,20,60,30,50,40]
- Explanation
- Pairs (10, 70), (20, 60), (30, 50) are woven together, and the middle node 40 ends up last.
Example 3
- Input:
- head = [5,9]
- Output:
- [5,9]
- Explanation
- First node then last node is already the current order, so nothing changes.
Constraints
- The number of nodes is in the range
[1, 5 * 10^4] 1 <= Node.val <= 1000