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: Given the head of a singly linked list, reverse the nodes k at a time and return the modified list. Nodes must be reversed by changing pointers, not values. If the remaining nodes are fewer than k, they stay in their original order.
This problem is a classic pointer manipulation exercise on a Linked List. The main challenge is correctly isolating groups of size k, reversing them, and reconnecting the groups without losing references.
Approach 1: Iterative Group Reversing (O(n) time, O(1) space)
The iterative approach walks through the list and processes one block of k nodes at a time. First check whether k nodes exist ahead; if not, stop because the remaining nodes should stay unchanged. Once a valid block is found, reverse the pointers inside that group using the standard linked list reversal technique (prev, curr, next). After reversing, connect the previous group's tail to the new head of the reversed segment.
A dummy node before the head simplifies edge cases, especially when the first group changes the list head. Each node is visited a constant number of times, giving O(n) time complexity and O(1) extra space. This approach relies entirely on pointer manipulation, making it a strong test of linked list fundamentals.
Approach 2: Recursive Group Reversal (O(n) time, O(n/k) recursion stack)
The recursive solution breaks the list into segments of size k. Start by checking whether at least k nodes exist. If they do, reverse the first k nodes locally. After the reversal, recursively process the remaining list starting from the k+1th node and attach the result to the tail of the reversed segment.
The key insight is that each recursive call handles exactly one block. The recursion naturally handles reconnection between segments, which simplifies the logic compared to iterative pointer tracking. Time complexity remains O(n) because each node participates in one reversal. Space complexity becomes O(n/k) due to the recursion call stack. This approach highlights how recursion can decompose a linked list problem into smaller identical subproblems.
Recommended for interviews: The iterative solution is what most interviewers expect. It achieves optimal O(n) time with O(1) space and demonstrates strong control over pointer operations in a linked list. Implementing the recursive variant afterward shows deeper understanding and comfort with recursive problem decomposition.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Group Reversing | O(n) | O(1) | Best for interviews and production code where constant extra space is required |
| Recursive Group Reversal | O(n) | O(n/k) | Good for understanding the divide-and-conquer structure of the problem and cleaner conceptual logic |
L21. Reverse Nodes in K Group Size of LinkedList • take U forward • 144,265 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