Reorder List

Reorder the list L0 → L1 → … → Ln−1 into L0 → Ln−1 → L1 → Ln−2 → L2 → … (first, last, second, second-last, …).

List format. A linked list is given as two lines: its length n, then its n values from head to tail (the second line is empty when n = 0). When you print a list, print its values on one line separated by spaces, or the word empty if it has no nodes.

Input: one list (n ≥ 1).

Output: the reordered list.

Constraints: 1 ≤ n ≤ 10⁵.

Challenge: do it on the nodes in O(1) extra memory by combining three classic moves: find the middle, reverse the second half, then merge the two halves alternately.