Reorder List

You are given the head of a singly linked list. The list can be represented as:

L0 -> L1 -> ... -> Ln-1 -> Ln

Reorder it to:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

The function modifies the list in-place and does not return a value.

---

Example 1

1 -> 2 -> 3 -> 4 -> null

becomes

1 -> 4 -> 2 -> 3 -> null

Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Explanation: The first node stays, then the last (4), then the second (2), then the third (3).

Example 2

1 -> 2 -> 3 -> 4 -> 5 -> null

becomes

1 -> 5 -> 2 -> 4 -> 3 -> null

Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: The middle node (3) ends up last; the list alternates front and back.

---

Constraints

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000