Reverse a Linked List in Groups of K
Company: Bytedance
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `reverse_k_group(values, k)` for a singly linked list represented by the array `values` in traversal order.
Reverse every consecutive group of exactly `k` nodes and return the resulting values. If fewer than `k` nodes remain at the end, preserve their original order. You may change links between existing nodes in a linked-list implementation, but not node values.
### Constraints
- `0 <= len(values) <= 200000`
- `1 <= k <= 200000`
- `-10^9 <= values[i] <= 10^9`
- Target `O(n)` time and `O(1)` auxiliary pointer space, excluding the returned array representation.
### Examples
- `[1, 2, 3, 4, 5]`, `k = 2` returns `[2, 1, 4, 3, 5]`.
- `[1, 2, 3, 4, 5]`, `k = 3` returns `[3, 2, 1, 4, 5]`.
- `[1, 2]`, `k = 1` returns `[1, 2]`.
```hint Confirm the group before changing it
Locate the kth node from the predecessor of the current group. If it does not exist, stop without modifying the suffix.
```
```hint Preserve the connections around a reversal
Track the node before the group, the original first node, and the first node after the group.
```
Quick Answer: Implement `reverse_k_group(values, k)` for a singly linked list represented by the array `values` in traversal order. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
The array `values` represents a singly linked list in traversal order. Reverse every consecutive group of exactly `k` nodes and return the resulting traversal values. If fewer than `k` nodes remain at the end, preserve that suffix in its original order. A linked-list implementation may change links between existing nodes but not values.
Constraints
- 0 <= len(values) <= 200000.
- 1 <= k <= 200000.
- Each value is an integer from -10^9 through 10^9.
- Only complete groups of exactly k are reversed; a shorter final suffix is unchanged.
Examples
Input: ([], 1)
Expected Output: []
Explanation: An empty traversal remains empty.
Input: ([7], 1)
Expected Output: [7]
Explanation: A singleton group of size one is unchanged.
Hints
- Test k = 1, k equal to the list length, and k greater than the list length.
- Include lengths both divisible and not divisible by k, especially a one-node remainder.
- Use duplicate, negative, and boundary values to confirm that only positions determine the result.