Reorder List
You are given the head of a singly linked list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be in the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only the nodes themselves may be changed.
Example 1
[1] -> [2] -> [3] -> [4] -> null --- [1] -> [4] -> [2] -> [3] -> null
Input
head = [1,2,3,4]Output
[1,4,2,3]The list is reordered from the ends inward as 1, then 4, then 2, then 3.
Example 2
[1] -> [2] -> [3] -> [4] -> [5] -> null --- [1] -> [5] -> [2] -> [4] -> [3] -> null
Input
head = [1,2,3,4,5]Output
[1,5,2,4,3]The list is reordered from the ends inward as 1, then 5, then 2, then 4, then 3.
Constraints
- The number of nodes in the list is in the range
[1, 5 * 10^4]. 1 <= Node.val <= 1000