Reverse Linked List in Groups of Size K
Problem Statement: Given a linked list, reverse the nodes of a linked list k at a time and return its 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.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
I hope you are clear with the understanding of the Given Problem Statement. In this article, we will discuss 2 approaches, one using Extra Space(Brute Force), and then we will optimize it and we will solve it in both iterative and Recursive Approach in constant space-time.
How to Approach this Problem?
Here, the first thing that comes in our mind is Reversing a part of LinkedList repeatedly. WHOO!! That’s right. We will reverse a group of K Sized LinkedList repeatedly. Now, several questions arise A. How do we link those groups after reversing it to reach the required Solution? B. Do we really need to reverse the last group having a size less than K(If the size is K, we will reverse but what if it is not ? How do we come to know?)
Well, now that you have asked these questions before jumping into the solution, you will definitely code it better. Let’s Solve It by answering the above questions.
Brute Force:
The first intuitive approach is you can reverse the group of LinkedList of size K and then store the new head of that reversed Group in an array. And we keep on doing this for all the possible K-sized Group in the given Linked List. But what if the group size is less than K, according to the problem statement we should not reverse it, so we can directly return and store the head Node of that group.
Let us consider an example to clarify this, consider a list 1 →2 →3 →4 →5–6 →None, K= 3. The solution to this should be 3 →2 →1 →6 →5 →4 →None. Now, if K=4, the solution should be 4 →3 →2 →1 →5 →6 →None.
So, every time we will check if the size of the group is less than K, if yes we will simply return the head else if we will return the new head. Now that we have the head nodes of each group, it is easy for us to traverse till its tail node and connecting it to the next head node present in the Array. (Connecting the groups).
If I consider the same example with K=3, we will have two groups i.e 1 →2 →3 and 4 →5 →6. So, we will reverse each group i.e 3 →2 →1, 6 →5 →4, and store the head nodes of each group i.e 3 and 6. Now, we will traverse the array(till n-1 index as we do not need to traverse the last group ) and get each head node. After that, I will traverse through that group up to tail i.e 1 and connect it to the next head node in array i.e 6. So, now my list is 3 →2 →1 →6 →5 →4 which is the required solution.
Brute Force works well as the Time Complexity is still O(N). But, Space Complexity is also O(N).In real-time, consider you will be having 1M nodes k=1(Worst Case), is it a good approach to store the 1M Nodes in your memory. The answer is No, so in this case, this approach is not good. Therefore we will have to do it in Constant Space i.e O(1) although time Complexity remains the same i.e O(N). But before diving into Optimized Version let us code the Brute Force Approach.
2.Optimized Approach (Constant Space):
As we know, LinkedList is playful in nature. We can just play with the links to get the required Solution. So, let us play with the links. The Approach remains the same. But here we will take advantage of the recursion to do the task which I mentioned in the above paragraph(Italicized) i.e we do not need to store the head nodes and recursion will connect the groups of Linked Lists. You can refer to the below image to get some idea of how recursion will work.
Let us check the code for the above approach:
Yuppie!! We are done but wait? Can you do this in the Iterative approach with constant space? Here I am posting the solution but make sure you do it on your own before checking out the solution.
This is a Hard Level Problem in Leetcode, which does not really seem tough. Let me know if you like this blog by clapping. Happy Coding!!
Problem Link:https://leetcode.com/problems/reverse-nodes-in-k-group/
