Reorder List

Given the head of a list L0 → L1 → … → Ln-1 → Ln, rearrange the nodes in place into:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Don't change node values, only the links. The function returns nothing; the test checks the list starting at head afterwards.

Example 1

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Example 3

Input: head = [10,20,30]
Output: [10,30,20]

Constraints

• 1 ≤ number of nodes ≤ 5 · 10⁴
• 1 ≤ Node.val ≤ 10⁵