Logicmojo - Updated Aug 28, 2021
Problem Statement: Reversing a Linked List in K-groups
reversing a Linked List Given a linked list and a positive number k, reverse the nodes in groups of k. All the remaining nodes after multiples of k should be left as it is.
Example:
k: 3
Linked list: 1→2→3→4→5→6→7→8→9
Result: 3→2→1→6→5→4→9→8→7
We have presented two approaches to solve the problem:
• Using - Recursion• Iterative Solution
Approach 1: Recursion
The first step is to check whether the Head is NULL or Not, if its NULL then we can directly return NULL
2. If the Head is not NULL, then we need to check the length of Linked List starting from current Head.
3. If it is not a multiple of K(Less than K) , then there is no need to reverse it and hence we can directly return head
4. Else if its a multiple of K, then we have to reverse the K elements starting from current Head
5. We will follow the same steps for the rest of the elements Recursively.
C++ Implementation:class Solution { public: ListNode* reverse(ListNode* first, ListNode* last) { ListNode* prev = last; while ( first != last ) { auto tmp = first->next; first->next = prev; prev = first; first = tmp; } return prev; } ListNode* reverseKGroup(ListNode* head, int k) { auto node=head; for (int i=0; i < k; ++i) { if ( ! node ) return head; // nothing to do list too sort node = node->next; } auto new_head = reverse( head, node); head->next = reverseKGroup( node, k); return new_head; } };
Python Implementation:
class Node: def __init__(self, val): self.val = val self.next = None def display(head): while head: print(head.val, end = ' -> ') head = head.next print('X') def reverse_k_group(head, k): pre = None ptr = head count = 0 while count < k and ptr: post = ptr.next ptr.next = pre pre = ptr ptr = post count += 1 if post: head.next = reverse_k_group(post, k) return pre if __name__=='__main__': head = Node(4) head.next = Node(2) head.next.next = Node(8) head.next.next.next = Node(5) head.next.next.next.next = Node(1) head.next.next.next.next.next = Node(6) head.next.next.next.next.next.next = Node(3) head.next.next.next.next.next.next.next = Node(7) print('Original List: ', end = '') display(head) head1 = reverse_k_group(head, 5) print('Reversed List: ', end = '') display(head1)
Time Complexity: O(n) Traversal of list is done only once and it has 'n' elements.
Auxiliary Space: O(n/k) For each Linked List of size n, n/k or (n/k)+1 calls will be made during the recursion.
Approach 2 Iterative Solution:
The iterative solution could be confusing because it always needs to manipulate a great number of pointers in this type of problems. However, though the implementation may seem a bit messed up, if we are clear what specific steps that we need to accomplish, then this is actually a straightforward problem.
1. Note that if the subsequent list from head does not contain k nodes, nothing needs to be changed. So we definitely need to check if there are still k nodes left. If there are, we proceed. Otherwise, the algorithm can halt.
2. Reverse the subsequent k consecutive nodes. In the meanwhile, keep track of the information of four nodes, the node before head, head, tail, and the node after tail.
3. At last, put the reversed sub-list back to the correct position, in between the the node before head (former head) and the node after the tail (former tail).
4. Move forward to reverse the next sub-list.
C++ Implementation:
class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(head==NULL||k==1) return head; int num=0; ListNode *preheader = new ListNode(-1); preheader->next = head; ListNode *cur = preheader, *nex, *tmp, *pre = preheader; while(cur = cur->next) num++; while(num>=k) { cur = pre->next; nex = cur->next; for(int i=1;i<k;i++) { tmp= nex->next; nex->next = pre->next; pre->next = nex; cur->next = tmp; nex = tmp; } pre = cur; num-=k; } return preheader->next; } };
Python Implementation:
class Node: def __init__(self, val=0, next=None): self.val = val self.next = next def display(head): while head: print(head.val, end = ' -> ') head = head.next print('X') def reverseKGroup(head, k): dummy = Node() dummy.next = head ptr = dummy count = 0 while head: count += 1 head = head.next tail = None curr = ptr.next for i in range(count//k): start = curr prev = None for _ in range(k): tmp = curr.next curr.next = prev prev = curr curr = tmp # To change new start if i == 0: ptr.next = prev # To connect the groups together if tail: tail.next = prev tail = start # for any leftover nodes if tail: tail.next = curr return dummy.next if __name__=='__main__': head = Node(4) head.next = Node(2) head.next.next = Node(8) head.next.next.next = Node(5) head.next.next.next.next = Node(1) head.next.next.next.next.next = Node(6) head.next.next.next.next.next.next = Node(3) head.next.next.next.next.next.next.next = Node(7) print('Original List: ', end = '') display(head) head1 = reverseKGroup(head, 2) print('Reversed List: ', end = '') display(head1)
Time Complexity: O(n) Traversal of list is done only once and it has 'n' elements.
Auxiliary Space: O(1)
With this article at Logicmojo, you must have the complete idea of solving Reverse Nodes in k-Group problem.