Reverse Nodes in k-Group
Last Updated: March 29, 2026
Understanding the Problem
This problem combines two classic linked list operations: counting nodes and reversing a sublist. The twist is that you need to do it repeatedly in chunks of exactly k nodes, and you have to leave the remainder alone if it's shorter than k.
Think of the linked list as a series of segments, each of length k. You reverse the nodes within each segment, then stitch the reversed segments back together. The tricky part is not the reversal itself, but the bookkeeping: keeping track of where each group starts, where it ends, and how to connect consecutive reversed groups without breaking the chain.
The key challenge is the "connection" between groups. When you reverse a group, its first node becomes the last and its last becomes the first. So the tail of the previous group needs to point to the new head of the current group, and the new tail of the current group needs to point to the head of the next group. Getting these pointers right is where most people get stuck.
Key Constraints:
1 <= k <= n <= 5000→ With n up to 5000, even O(n^2) would be around 25 million operations, well within limits. But since we're doing linked list pointer manipulation, the natural approach is O(n) anyway.0 <= Node.val <= 1000→ Node values are non-negative. This doesn't affect the algorithm since we're rearranging nodes, not values.You may not alter the values→ We must physically move nodes by changing pointers, not just swap values. This is an important constraint that eliminates the simpler "swap values" approach.
Approach 1: Extract to Array and Rebuild
Intuition
The most straightforward way to think about this: pull all the values out of the linked list into an array, reverse each k-sized chunk in the array, then rebuild the linked list from the modified array.
Arrays make group reversal trivial because you can access any element by index. You just swap elements within each group of k. The downside is that this uses O(n) extra space and technically violates the constraint of not altering values (since we're reading values out and writing them back). But it's a clean starting point that makes the logic easy to follow.
Algorithm
- Traverse the linked list and collect all node values into an array.
- For each chunk of k elements in the array (starting at indices 0, k, 2k, ...), reverse the chunk in place. If the last chunk has fewer than k elements, leave it alone.
- Walk through the linked list again, overwriting each node's value with the corresponding value from the modified array.
- Return the head.
Example Walkthrough
Input:
After collecting into array and reversing groups of 2:
Write values back to linked list:
Code
- Time Complexity: O(n). We traverse the list once to collect values, reverse chunks in the array, and write values back. Each pass is O(n).
- Space Complexity: O(n). We store all node values in an array of size n.
This approach works correctly but uses extra space and modifies node values. What if we reversed the nodes themselves by manipulating pointers, using O(1) extra space?
Approach 2: Iterative In-Place Reversal
Intuition
The real way to solve this problem is to reverse the actual node pointers within each group. No arrays, no value swapping, just pointer manipulation.
Here's the plan: use a dummy node before the head to simplify edge cases. Then, for each group, check if there are k nodes remaining. If yes, reverse those k nodes in place using the standard linked list reversal technique (prev/curr/next pointers). After reversing, reconnect the group to the rest of the list. The original first node of the group is now the tail, and the original last node is the new head.
The dummy node is crucial. Without it, the first group is a special case because there's no "previous group tail" to update. With a dummy node, every group, including the first, has a consistent predecessor.
The key insight is that reversing k nodes in a linked list is the same as the classic "reverse a linked list" problem, just limited to k iterations instead of running until null. By initializing prev to groupNext (the node after the group), the reversed portion automatically connects to the rest of the list.
The dummy node ensures that groupPrev always has a valid predecessor, even for the first group. After each reversal, the original first node of the group becomes the tail, which serves as groupPrev for the next iteration. This creates a clean loop that handles any number of groups uniformly.
Algorithm
- Create a dummy node that points to
head. SetgroupPrev = dummy. - While there are nodes to process:
a. Check if at least k nodes remain from the current position. If not, break.
b. Identify the k-th node of the current group.
c. Save the node after the group as groupNext.
d. Reverse the k nodes within the group using standard reversal (prev/curr/next).
e. Reconnect: groupPrev.next points to the new head, and the new tail points to groupNext.
f. Advance groupPrev to the new tail (the original first node of this group).
- Return
dummy.next.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited at most twice: once during the k-count check and once during the actual reversal. Across all groups, that's 2n operations total.
- Space Complexity: O(1). Only a constant number of extra pointers are used. No recursion, no auxiliary data structures.
This iterative approach satisfies the O(1) space follow-up. But can we express the same logic more elegantly using recursion?
Approach 3: Recursive Reversal
Intuition
Recursion offers a more elegant way to think about this problem. The idea is: reverse the first k nodes, then recursively call the function on the remaining list. The base case is when fewer than k nodes remain, in which case you return the list as-is.
The recursive approach is cleaner conceptually because each call only worries about one group. The connection between groups happens naturally through the return value: the recursive call returns the head of the already-processed remainder, and we connect the tail of our reversed group to it.
The trade-off is space. Each recursive call adds a frame to the call stack, so we use O(n/k) stack space. For small k values (like k=1 or k=2), this could be O(n) extra space, which doesn't satisfy the follow-up. But it's worth knowing for interviews because it's often easier to code correctly under pressure.
The recursion mirrors how we naturally think about the problem: "reverse this group, then let someone else handle the rest." The recursive call returns the head of the correctly processed remainder, which we simply attach to the tail of our reversed group.
The counting step before reversal ensures we never reverse an incomplete group. If count < k, we return the head unchanged, which correctly leaves the last partial group in its original order. We don't need a dummy node or complex reconnection logic because the recursive return value handles the stitching automatically.
Algorithm
- Count the number of nodes from the current head. If fewer than k, return head as-is (base case).
- Reverse the first k nodes using the standard reversal technique.
- The original head is now the tail of the reversed group. Set
head.nextto the result of recursively callingreverseKGroupon the (k+1)-th node. - Return the new head of the reversed group (the k-th node from the original).
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited at most twice (once for counting, once for reversal). The total work across all recursive calls is O(n).
- Space Complexity: O(n/k). The recursion depth is n/k (one call per group). In the worst case (k=1), this becomes O(n).