Reverse Nodes in k-Group
Understanding the Problem
This problem combines two linked list operations: counting nodes and reversing a sublist. The difference from a plain reversal is that you do it repeatedly in chunks of exactly k nodes, and you leave the remainder alone if it is shorter than k.
The list is a series of segments, each of length k. You reverse the nodes within each segment, then connect the reversed segments back together. The difficulty is not the reversal itself but the bookkeeping: tracking where each group starts, where it ends, and how to connect consecutive reversed groups without breaking the chain.
The connection between groups is the main hazard. When you reverse a group, its first node becomes the last and its last becomes the first. The tail of the previous group must point to the new head of the current group, and the new tail of the current group must point to the head of the next group.
Key Constraints:
1 <= k <= n <= 5000→ The list always has at least k nodes, so at least one full group is reversed. An O(n) single-pass-per-group solution is straightforward here, so there is no reason to settle for anything slower.0 <= Node.val <= 1000→ Values are small and non-negative, but this does not affect the algorithm since we rearrange nodes, not values.You may not alter the values→ We must move nodes by changing pointers, not by swapping values. This rules out the "copy values into an array, reverse, copy back" shortcut as a true solution, though it remains a useful warm-up for the logic.
Approach 1: Extract to Array and Rebuild
Intuition
Pull all the values out of the linked list into an array, reverse each k-sized chunk in the array, then write the values back into the list nodes in their new order.
An array makes group reversal direct because you can index any element. To reverse a group, swap elements within each window of k. This uses O(n) extra space and rewrites node values rather than moving nodes, so it does not satisfy the follow-up. It is a starting point that separates the reordering logic from the pointer-juggling, which the next two approaches handle properly.
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
Take head = [1, 2, 3, 4, 5] with k = 2.
Step 1, collect values: traverse the list and copy each value, giving values = [1, 2, 3, 4, 5] and n = 5.
Step 2, reverse complete groups. The loop runs for start = 0 and start = 2, since start + k <= n requires start <= 3. At start = 4, only one element remains (4 + 2 = 6 > 5), so that final group is left untouched.
start = 0: reversevalues[0..1], swapping1and2. Array becomes[2, 1, 3, 4, 5].start = 2: reversevalues[2..3], swapping3and4. Array becomes[2, 1, 4, 3, 5].start = 4: skipped, leaving the trailing5in place.
Step 3, write values back: walk the original nodes and overwrite their values in order, producing the list 2 -> 1 -> 4 -> 3 -> 5.
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.
The next approach reverses the nodes themselves through pointer manipulation, using O(1) extra space and satisfying the follow-up.
Approach 2: Iterative In-Place Reversal
Intuition
Reverse the actual node pointers within each group. No array, no value copying.
The plan: use a dummy node before the head to remove the first-group edge case. For each group, check whether k nodes remain. If they do, reverse those k nodes in place using the standard linked list reversal (prev/curr/next pointers). After reversing, reconnect the group to the rest of the list. The original first node of the group is now its tail, and the original last node is its new head.
The dummy node matters because without it the first group is a special case, with no preceding tail to update. With a dummy node, every group including the first has a predecessor to point at the reversed head.
Reversing k nodes is the standard list-reversal loop stopped after exactly k iterations instead of running to null. Initializing prev to groupNext (the node after the group) rather than to null means the last node processed during reversal ends up pointing at groupNext, so the reversed segment already connects to the rest of the list. No separate "fix the tail" step is needed.
After each reversal, the original first node of the group is now its tail, and it becomes groupPrev for the next iteration. The loop therefore handles any number of groups with the same body.
Algorithm
- Create a dummy node that points to
head. SetgroupPrev = dummy. - While there are nodes to process:
- Check if at least k nodes remain from the current position. If not, break.
- Identify the k-th node of the current group.
- Save the node after the group as
groupNext. - Reverse the k nodes within the group using standard reversal (prev/curr/next).
- Reconnect:
groupPrev.nextpoints to the new head, and the new tail points togroupNext. - Advance
groupPrevto 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. The same logic can also be expressed recursively, which trades the explicit reconnection bookkeeping for stack space.
Approach 3: Recursive Reversal
Intuition
Reverse the first k nodes, then recursively call the function on the remaining list. The base case is fewer than k nodes remaining, where the list is returned unchanged.
Each call handles exactly one group. The connection between groups comes through the return value: the recursive call returns the head of the already-processed remainder, and the tail of the current reversed group is connected to it.
The trade-off is space. Each recursive call adds a frame to the call stack, so this uses O(n/k) stack space. For small k (k=1 or k=2), that is O(n), which does not satisfy the O(1) follow-up.
After reversing the first k nodes, head (the original first node) is now this group's tail, and prev is its new head. Setting head.next to reverseKGroup(curr, k) attaches the fully processed remainder to that tail, and returning prev hands the new head up to the caller, which connects it as the previous group's successor.
The counting step before reversal prevents reversing an incomplete group. When count < k, the head is returned unchanged, leaving the last partial group in its original order. The return value supplies each connection, so no dummy node or explicit reconnection is required.
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).