Watch 10 video solutions for Reverse Nodes in k-Group, a hard level problem involving Linked List, Recursion. This walkthrough by take U forward has 144,265 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]
Constraints:
n.1 <= k <= n <= 50000 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
Problem Overview: You are given the head of a singly linked list and an integer k. Reverse the nodes of the list k at a time. If the number of remaining nodes is less than k, leave them as they are. Node values cannot be modified; only pointers can be changed.
This problem tests pointer manipulation on a linked list. The key challenge is reversing exactly k nodes at a time while reconnecting the reversed segments back into the original list.
Approach 1: Iterative Group Reversing (O(n) time, O(1) space)
Traverse the list and process it in fixed-size groups of k. First, check whether k nodes exist ahead using a pointer scan. If fewer than k nodes remain, stop and keep them unchanged. When a valid group is found, reverse the k nodes using the standard in-place linked list reversal technique: iterate through the group and redirect next pointers one by one.
After reversing a group, reconnect three parts: the previous group's tail, the new head of the reversed group, and the next group's starting node. A dummy node before the head simplifies edge cases where the first group gets reversed. This approach touches each node a constant number of times, giving O(n) time complexity and O(1) extra space. This is the most common production-style implementation.
Approach 2: Recursive Group Reversal (O(n) time, O(n/k) recursion stack)
The recursive approach treats the list as repeating blocks of size k. First verify that k nodes exist. If they do, reverse the first k nodes using an iterative reversal loop. After reversing the block, recursively process the remainder of the list starting from the (k+1)th node.
The original head of the block becomes the tail after reversal. Connect this node to the result returned by the recursive call. Each recursive frame processes exactly one block of size k, so the total work remains O(n). The recursion stack depth is about n/k, which gives O(n/k) auxiliary space.
This approach reads naturally because each call solves one block and delegates the rest. It is a good demonstration of recursion applied to pointer structures, though it uses extra stack space compared to the iterative version.
Recommended for interviews: The iterative group-reversal approach is typically expected. It demonstrates strong control over pointer manipulation, constant-space optimization, and careful handling of boundary conditions. Showing the recursive idea first can communicate conceptual clarity, but the iterative solution proves you can implement an optimal O(n) and O(1) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Group Reversing | O(n) | O(1) | Best general solution. Constant extra space and commonly expected in interviews. |
| Recursive Group Reversal | O(n) | O(n/k) | Useful when recursion makes the logic easier to express or when demonstrating recursive linked list manipulation. |