Linked ListFast and Slow PointersPointer Reversal
Reorder a linked list L0 -> L1 -> ... -> Ln so that it reads L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... Do it by changing links, not by copying values. The values are given as an array; build the linked list from them yourself, then solve it with pointers.
Input
Line 1: n. Line 2: the n node values.
Output
Print the reordered list's values on one line.
Constraints
1 <= n <= 5 * 10^4
Example 1
Input
4 1 2 3 4
Output
1 4 2 3
First, last, second, second-last: 1 4 2 3.
Example 2
Input
5 1 2 3 4 5
Output
1 5 2 4 3
1 5 2 4 3.