589. LinkedList Reordering
Given the head of a singly linked-list, reorder the list in a specific pattern. The list is represented as L0 -> L1 -> ... -> Ln-1 -> Ln. The reordered list should follow the pattern L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... . Only the order of the nodes can be changed, not their values.
The first line of input contains an integer N, the number of nodes in the list. The second line contains N space-separated integers, representing the values of the nodes.
Print the list after reordering it.
4 1 2 3 4
1 4 2 3
The number of nodes in the list is between 1 and 50,000 inclusive. Each node's value is between 1 and 1,000 inclusive.