333. Ends Inward
A choir stands in a line stored as a chain: each node holds a singer's height and a link to the next singer, and head is the first one. The director wants them re-lined from the ends toward the middle: first the original first singer, then the original last, then the second, then the second to last, and so on until everyone is placed.
Rewrite the chain in place into this order. The function returns nothing; after it ends, following the links from head must show the new order. For a chain L0, L1, ..., Ln-1 the result is L0, Ln-1, L1, Ln-2, L2, .... Relink the existing nodes; the head node stays the head. Chains of length 0, 1 or 2 are already in the required order.
Example 1
- Input:
- head = [1,2,3,4,5,6,7]
- Output:
- [1,7,2,6,3,5,4]
- Explanation:
Alternate from the two ends: 1, 7, 2, 6, 3, 5, 4.
Example 2
- Input:
- head = [60,50,40,30]
- Output:
- [60,30,50,40]
- Explanation:
First 60, last 30, then 50, then 40: 60, 30, 50, 40.
Constraints
0 ≤ chain length ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
headafter your method returns. - Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)