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.
Use an iterative approach to reverse each group of k nodes separately. This approach leverages an auxiliary dummy node and previous and current pointers to manage the connections at each step. We traverse the list, checking for complete sets of k nodes to reverse them. If a group of nodes has less than k nodes, leave them as they are.
We count length of the list to check if a full k group exists. A dummy node facilitates manipulation of edge connections. For each complete k-length, we perform a series of node swaps. We adjust prev, current, and next pointers accordingly to achieve the reversal.
Time Complexity: O(n), where n is the number of nodes in the list, as each node is processed once.
Space Complexity: O(1), since no extra space is used apart from pointers.
Recurse through the linked list, reversing k nodes at a time. If a full group of k nodes is found, reverse and connect through recursive calls. Terminate when fewer than k nodes are left. This approach inherently uses the call stack for management of reverse sequences.
This recursive function inclusively reverses k nodes using a helper function and connects subsequent recursions via the next pointer. The recursion unwinds back, each time ending with any remaining nodes less than k in original order.
Time Complexity: O(n), since we process each node once even recursively.
Space Complexity: O(n/k), the recursion depth in worst case equals the number of complete k-sized groups.
We can simulate the entire reversal process according to the problem description.
First, we define a helper function reverse to reverse a linked list. Then, we define a dummy head node dummy and set its next pointer to head.
Next, we traverse the linked list, processing k nodes at a time. If the remaining nodes are fewer than k, we do not perform the reversal. Otherwise, we extract k nodes and call the reverse function to reverse these k nodes. Then, we connect the reversed linked list back to the original linked list. We continue to process the next k nodes until the entire linked list is traversed.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Group Reversing | Time Complexity: O(n), where n is the number of nodes in the list, as each node is processed once. |
| Recursive Group Reversal | Time Complexity: O(n), since we process each node once even recursively. |
| Simulation | — |
| 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. |
Reverse Nodes in K-Group - Linked List - Leetcode 25 • NeetCode • 168,817 views views
Watch 9 more video solutions →Practice Reverse Nodes in k-Group with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor