A toy train is stored as a singly linked list of n coaches. Reverse the coaches from position m to position k (1-based, inclusive), leaving the rest in place, by relinking nodes in one pass.
Print the train from front to back.
Constraints
- 1 ≤ m ≤ k ≤ n ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n integers (coach numbers, front first). Line 3: m and k.
- Output
- The n values after the reversal, space-separated.
Examples
Input 1
6
10 20 30 40 50 60
2 5Output
10 50 40 30 20 60Nodes 2 to 5 (20, 30, 40, 50) are reversed in place.
Input 2
3
7 8 9
1 3Output
9 8 7Reversing positions 1 to 3 reverses the whole list.
Show hints
- Use a dummy node in front of the head so reversing from position 1 needs no special case.
- Walk to the node just before position m, then move the next node to the front of the section k − m times.
Show the explanation
Put a dummy node before the head and walk to the node prev just before position m. Let cur be the first node of the section. Repeat k − m times: take the node after cur out and insert it right after prev. Each step moves one more node to the front of the section, reversing it in place. One pass and O(1) extra space; the dummy node handles m = 1 without special code.
Original UniCircle question. Last reviewed 22 Oct 2026.