292. Turn the Chain Around
A railway yard stores its wagons as a chain: every wagon holds a number and a link to the wagon behind it, and the first wagon is called head. The depot manager wants the whole train driven out in the opposite direction, so the last wagon leads and the first wagon trails.
Given the head of the chain, turn the chain around and return the new head. Reuse the existing wagons by redirecting their links; do not build a second chain from copies. An empty chain stays empty, and a one-wagon chain is unchanged. The chain can hold up to 100,000 wagons, so think about whether deep recursion is safe in your language.
Example 1
- Input:
- head = [10,20,30,40]
- Output:
- [40,30,20,10]
- Explanation:
Reading the chain backwards gives 40, 30, 20, 10.
Example 2
- Input:
- head = [5]
- Output:
- [5]
- Explanation:
A single node is its own reverse.
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.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)