Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/reverse-nodes-in-k-group
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:
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1)
extra memory space?
Explanation
Reverse a linked list
We can use the standard Reverse linked list code with a slight modification. We pass the count k
to the method, which reverses the sublist of size k
. We should keep the track of the next node and the previous node. These are required to point the pointers of the current sublist correctly to our previous sublist.
A C++ snippet of this approach is as follows:
ListNode* reverse(ListNode* head, int k) {
if (!head)
return NULL;
ListNode* current = head;
ListNode* next = NULL;
ListNode* prev = NULL;
int count = 0;
while (current != NULL && count < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if (next != NULL)
head->next = reverse(next, k);
return prev;
}
The time complexity of this approach is O(n). The space complexity is O(n / k). For a linked list of size n, we make n/k
or n/k + 1
calls during recursion.
Optimized solution: Iterative
We can optimize the space by using the above approach without recursion. We keep track of the previous, current, and next nodes while reversing the linked list in a set of size k
. Once the sublist of size k
is reversed we update the previous, current, and next node correctly. We repeat this approach till the list is traversed or the last sublist is less than size k
.
Let's check the algorithm
Algorithm
- if !head || k == 1
- return head
- set ListNode *temp = new ListNode(1)
temp->next = head
- set ListNode *prev, *current, *next = temp
set count = 0
initialize index and i variables
// count the size of the list
- loop while current
- current = current->next
- count++
- while end
- loop while next
- set current = prev->next
- set next = current->next
// if the last sublist is less than size k
// we keep the list as it is.
// Hence setting index = 0.
- index = count > k ? k : 0
- loop for i = 1; i < index; i++
- set current->next = next->next
next->next = prev->next
prev->next = next
next = current->next
- for end
- set prev = current
- update count = count - k
- for end
- return temp->next
The time complexity of the above approach is O(n). The space complexity is O(1).
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(!head || k == 1) {
return head;
}
ListNode *temp = new ListNode(1);
temp->next = head;
ListNode *prev = temp, *current = temp, *next = temp;
int count = 0, index, i;
while(current) {
current = current->next;
count++;
}
while(next) {
current = prev->next;
next = current->next;
index = count > k ? k : 0;
for(i = 1; i < index; i++) {
current->next = next->next;
next->next = prev->next;
prev->next = next;
next = current->next;
}
prev = current;
count -= k;
}
return temp->next;
}
};
Golang solution
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
return head
}
temp := &ListNode{1, nil}
temp.Next = head
prev, current, next := temp, temp, temp
count, index, i := 0, 0, 0
for current != nil {
current = current.Next
count++
}
for next != nil {
current = prev.Next
next = current.Next
if count > k {
index = k
} else {
index = 0
}
for i = 1; i < index; i++ {
current.Next = next.Next
next.Next = prev.Next
prev.Next = next
next = current.Next
}
prev = current
count -= k
}
return temp.Next
}
JavaScript solution
var reverseKGroup = function(head, k) {
if(!head || k == 1) {
return head;
}
let temp = new ListNode(1, null);
temp.next = head;
let prev = temp, current = temp, next = temp;
let count = 0, index, i;
while(current) {
current = current.next;
count++;
}
while(next) {
current = prev.next;
next = current.next;
index = count > k ? k : 0;
for(i = 1; i < index; i++) {
current.next = next.next;
next.next = prev.next;
prev.next = next;
next = current.next;
}
prev = current;
count -= k;
}
return temp.next;
};
Let's dry-run our algorithm to see how the solution works.
Input: head = [1, 2, 3, 4, 5]
k = 2
Step 1: if !head || k == 1
head -> [1, 2, 3, 4, 5] || 3 == 1
false
Step 2: temp = new ListNode(1)
-> [1]
temp->next = head
temp -> [1, 1, 2, 3, 4, 5]
head -> [1, 2, 3, 4, 5]
Step 3: ListNode *prev = temp, *current = temp, *next = temp
count = 0
index, i
Step 4: loop while current
current = current->next
count++
This will count the size of linked list.
count = 5
Step 5: loop while next
current = prev->next
= [1, 2, 3, 4, 5]
next = current->next
= [2, 3, 4, 5]
index = count > k ? k : 0
= 5 > 2 ? 2 : 0
= 2
loop for i = 1; i < 2
1 < 2
true
current->next = next->next
= [3, 4, 5]
next->next = prev->next
= [1, 3, 4, 5]
prev->next = next
= [2, 1, 3, 4, 5]
next = current->next
= [3, 4, 5]
i++
i = 2
loop for i < 2
2 < 2
false
prev = current
= [1, 3, 4, 5]
count = count - k
= 5 - 2
= 3
Step 6: loop while next
next = [3, 4, 5]
current = prev->next
= [3, 4, 5]
next = current->next
= [4, 5]
index = count > k ? k : 0
= 3 > 2 ? 2 : 0
= 2
loop for i = 1; i < 2
1 < 2
true
current->next = next->next
= [3, 5]
next->next = prev->next
= [1, 4, 5]
prev->next = next
= [4, 3, 5]
next = current->next
= [5]
i++
i = 2
loop for i < 2
2 < 2
false
prev = current
= [5]
count = count - k
= 3 - 2
= 1
temp = [2, 1, 4, 3, 5]
Step 7: loop while next
next = [5]
current = prev->next
= [5]
next = current->next
= nil
index = count > k ? k : 0
= 1 > 2 ? 2 : 0
= 0
loop for i = 1; i < 0
1 < 0
false
prev = current
= [5]
count = count - k
= 1 - 2
= -1
Step 8: loop while next
next = nil
false
Step 9: return temp->next
temp = [1, 2, 1, 4, 3, 5]
temp->next = [2, 1, 4, 3, 5]
We return the answer as [2, 1, 4, 3, 5].
Top comments (0)