#172MediumLinked Lists· Middle, Reverse, Interleave

Reorder Train Cars

A freight train is stored as a singly linked list of cars, front to back: `c0 -> c1 -> c2 -> ... -> c(n-1)`. To balance the load on a bridge, the yard master wants the cars rearranged so that the first car is followed by the last, then the second car, then the second-to-last, and so on: `c0 -> c(n-1) -> c1 -> c(n-2) -> c2 -> ...` Rearrange the list **in place** by changing links only: do not create new nodes and do not just overwrite the values. Return the head of the rearranged list.

Input format

`head`: the head of a singly linked list, given as an array of integers (possibly empty).

Output format

The rearranged list as an array.

Examples

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

Output: [1, 4, 2, 3]

Alternate between the front and back: 1, 4, 2, 3.

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

Output: [1, 5, 2, 4, 3]

With an odd length the middle car 3 ends up last: 1, 5, 2, 4, 3.

Input: head = [8]

Output: [8]

A list with one car is already in the required order.

Constraints

0 <= number of nodes <= 5 * 10^4
-1000 <= node value <= 1000

#linked-list
#two-pointers
#in-place