Reverse Every K-Elements Sublist Of Linked List | Coding Interview | Hard (not so much)
This article is similar to the one we did before ( i.e., Reverse the linked list). A slight difference makes it more challenging, though. It has been asked by many companies (And I mean it…) like Accolite, Adobe, Hike, Microsoft, and many more.
It is normal to be asked some system design questions during interviews. I have written an article summarising essential topics in the field.
Description
Given a linked list, we have to reverse the list in subsets of size K. In other words, take the first K nodes and reverse them, then, take the subsequent K nodes and reverse them too, and so on.
More Sample Examples:
Input: 2->5->3->6->8->9, K = 3
Output: 3->5->2->9->8->6
Explanation: We are taking 3 consecutive nodes at a time and reversing
them. So, 2, 5, and 3 are reversed, and 6, 8, and 9 are reversed.Solution
If you know the method to reverse a complete linked list, then you can apply the same technique here, just apply it on k nodes at a time. In other words, use three pointers, current for current node, next for next node and prev for previous node.
Then use a while loop for reversing the k nodes and run it till current node is not null, and count of nodes reversed so far is not k.
// commented, easy to understand code.
Node *current = head;
Node *next = nullptr;
Node *prev = nullptr;
int count = 0;
// reverse first k nodes of the linked list
while (current != nullptr && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}Explanation: We defined the three nodes to point to current, next and previous (prev) node. In the while loop, we save the next node of the current node in the next pointer and set the next pointer of current node to point the previous node.
The prev pointer then points to the current node before we make the next node our new current node. In the end, we increase the counter to count how many nodes have been reversed.
You will notice that after the while loop, the next pointer points to the first node of unreversed linked list and prev points to the head of the reversed node.
In the end, we will check if the next node is null, if it is not, then we will call the reverse function recursively on the remaining part of the linked list. And end the function by returning the prev pointer, why? because it’s the head of the reversed sublist. The complete function will look something like this.
// Commented, easy to understand code.
Node *reverse(Node *head, int k)
{
// base case
if (!head)
return nullptr;
Node *current = head;
Node *next = nullptr;
Node *prev = nullptr;
int count = 0;
// reverse first k nodes of the linked list
while (current != nullptr && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is the pointer to the first node of the un reveresed node */
if (next != nullptr)
head->next = reverse(next, k);
// return the head of the reversed node
return prev;
}
/*
When called it will return the new head pointer where the linked list would
have been reversed using k nodes at a time.
*/Time & Space Complexity
Time: The while loop runs for at most n/k times, and the function itself is called k times. Hence, the time complexity is n/k * k, which is O(n).
Space: We didn’t use any data structure to solve the problem, but since we made the k recursive calls to the reverse function, it can be said to be O(k) in terms of space complexity.
Thanks.
To connect ✋🏽or hire: LinkedIn
If you liked what you just read, a clap 🤗🤗🤗would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment😋!
P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and supports all the writers.
You can also follow me HERE to get updates on the stories that I write.
