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 <= 1000Follow-up: Can you solve the problem in O(1) extra memory space?
Reverse Nodes in k-Group requires reversing nodes of a linked list in fixed groups of size k while preserving the order of remaining nodes if fewer than k remain. The main challenge is managing pointers carefully while processing the list in segments.
A common strategy is to first check whether k nodes exist ahead. If they do, reverse that segment of the linked list and reconnect it with the previous and next parts of the list. This can be implemented iteratively using pointer manipulation or recursively by solving one group and calling the function on the remainder.
The iterative approach typically uses a dummy node and pointer tracking to simplify reconnections. The recursive method focuses on reversing the first k nodes and then linking the result to the recursive call on the rest of the list. Both strategies traverse the list once, making them efficient for large inputs.
Time complexity is linear since each node is processed once, while space complexity depends on whether recursion is used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative k-group reversal | O(n) | O(1) |
| Recursive k-group reversal | O(n) | O(n) (recursion stack) |
take U forward
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.
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.
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode* next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9class Solution {
10public:
11 ListNode* reverseKGroup(ListNode* head, int k) {
12 if (!head || k == 1) return head;
13 ListNode dummy(0);
14 dummy.next = head;
ListNode* prev = &dummy;
ListNode* current = head;
int len = 0;
while (current) {
len++;
current = current->next;
}
while (len >= k) {
current = prev->next;
ListNode* next = current->next;
for (int i = 1; i < k; ++i) {
current->next = next->next;
next->next = prev->next;
prev->next = next;
next = current->next;
}
prev = current;
len -= k;
}
return dummy.next;
}
};
This implementation uses a similar approach to the C solution. A dummy node is initiated to ease node relinking operations. We loop through the list, checking if sufficient nodes remain to perform a k-group reversal, and adjust node pointers to reverse each k-group.
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.
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.
1 public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
current = ReverseKGroup(current, k);
while (count-- > 0) {
ListNode tmp = head.next;
head.next = current;
current = head;
head = tmp;
}
head = current;
}
return head;
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Checking for k nodes ensures that only complete groups are reversed. If fewer than k nodes remain at the end of the list, they must stay in their original order according to the problem constraints.
Yes, Reverse Nodes in k-Group is a well-known hard linked list problem that has appeared in interviews at top tech companies. It tests understanding of pointer manipulation, linked list traversal, and careful handling of edge cases.
A singly linked list is the core data structure used in this problem. The solution relies heavily on pointer manipulation to reverse segments and reconnect them without creating extra data structures.
The optimal approach processes the linked list in segments of size k and reverses each group using pointer manipulation. An iterative method with a dummy node is commonly used because it allows efficient reconnection between reversed segments. This approach runs in O(n) time with O(1) extra space.
The C# solution recursively assesses full k-group potentials, reversing such sequences whilst preserving non-k-alignable endings. Through recursion unwinding, each full group is recursively modified and connected correctly through node pointer modifications.