Given the head of a singly linked list, reorder it to follow the pattern L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...
Return the reordered list.
For the Cheetcode runner, linked lists are represented as plain arrays in node order.
Work with node references instead of array indexes. Make sure you preserve the next pointers you still need before changing links.
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
- The number of nodes in the list is in the range [1, 50,000].
- 1 <= Node.val <= 1,000