Reverse linked list in group of K
In previous post reversing a linked list, we learned and coded for reversing entire linked list. This problems is bit different, here we have to reverse linked list but in batches of size K. It means we need to reverse first K nodes of linked list then next K nodes and so on. Below examples show what is expected out of code you write for this problem reverse linked list in group of K.
1->2->3->4->5->6->NULL batch size = 2 Output: 2->1->4->3->6->5->NULL Similarly 1->2->3->4->5->6->NULL batch size = 4 Output: 4->3->2->1->6->5->NULL
Hope above example clarifies the requirement. Now, let see the mechanism to solve this.
Reverse a linked lists in group of K: Algorithm
There are two things, we should note in this problem : First that it can be solved recursively, as we solve reversing of entire linked list. Reverse first K nodes and then apply the same for rest of sub linked list, till the time only one node or NULL linked list is encountered.
Second thing is to figure out how to connect two parts which we got in first step. Note that head of first K nodes which are reversed will be last node in output linked list. What should be next pointer of this node? Yes, it should be last node of next batch which will be reversed. Hence we can connect head node of current batch to last node of next batch. Last node of next batch will be returned by recursive call we make (previous node when we reverse K nodes).
Now that we know how to split and combine parts of problem to solve it, let’s see algorithm to reverse a linked list in group of given size:
1. Reverse first K nodes. Keep track of previous node, to be returned. 2. Connect head of these K nodes to previous node returned. head->next = reverseListInBatches(next, K); 3. Return previous node, i.e last node of these K nodes. At the end of recession, last previous returned will become head of linked list.
Reverse linked list in group size K implementation
Original list :8->7->6->5->4->3->Null Reverse list :7->8->5->6->3->4->Null
Test 1: NULL list Test 2: List with only one node Test 3: Linked list with 6 nodes and batch size of 2 Test 4: Linked list with 5 nodes and batch size of 2
Complexity of code to reverse linked list in group of K is O(n). There is inherent space complexity of O(n/K) due to recursion. If n is too large and K is too small, there is risk of stack overflow.
To avoid that extra space usage, we can go for iterative implementation. Below is iterative implementation of reverse linked list in group of K nodes
Please leave comment or suggestion if you see something can be improved or something is wrong. And all the best.