A relay team stands as a singly linked list L0 → L1 → … → Ln−1. The coach wants them reordered as L0 → Ln−1 → L1 → Ln−2 → L2 → …, alternating from the front and the back. Do it by relinking nodes (O(1) extra space), then print the new order.
Constraints
- 1 ≤ n ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- The n values in the new order, space-separated.
Examples
Input 1
5
1 2 3 4 5Output
1 5 2 4 3Take from the front and back in turn: 1, 5, 2, 4, 3.
Input 2
4
10 20 30 40Output
10 40 20 30Even length: 10, 40, 20, 30.
Show hints
- Find the middle with slow/fast pointers.
- Reverse the second half.
- Merge the two halves by alternating nodes.
Show the explanation
Three classic linked-list moves combine here. (1) Find the middle with a slow pointer (one step) and a fast pointer (two steps). (2) Cut the list after the middle and reverse the second half. (3) Interleave: take one node from the first half, one from the reversed second half, and repeat. Each step is O(n) and needs only a few pointers.
Original UniCircle question. Last reviewed 22 Oct 2026.