307. Reverse in Batches
A conveyor belt carries parcels stored as a chain, each node holding a parcel weight. The packers work in batches of exactly k consecutive parcels: they take a batch off the belt and put it back in the opposite order. Batches are formed from the front of the chain, one after another.
Given the head of the chain and an integer k, reverse the order of every complete batch of k nodes and return the new head. If fewer than k nodes remain at the end, that last partial batch stays exactly as it is. Rearrange the nodes by changing their links; changing node values is not allowed to be the whole solution idea. The chain can hold up to 100,000 nodes, and k = 1 leaves the chain unchanged.
Example 1
- Input:
- head = [11,22,33,44,55,66,77], k = 3
- Output:
- [33,22,11,66,55,44,77]
- Explanation:
The complete batches are (11, 22, 33) and (44, 55, 66), which become (33, 22, 11) and (66, 55, 44). The leftover 77 stays: [33, 22, 11, 66, 55, 44, 77].
Example 2
- Input:
- head = [4,8,15,16,23], k = 2
- Output:
- [8,4,16,15,23]
- Explanation:
Batches (4, 8) and (15, 16) are reversed, and 23 is a short batch left alone: [8, 4, 16, 15, 23].
Constraints
0 ≤ chain length ≤ 105
1 ≤ k ≤ max(1, chain length)
-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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)