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.