Reverse the given Linked List is Group of given size K.
For example,

This problem similar to Reverse a Linked List problem. But instead of reversing Linked List from starting to end, we reverse the first K nodes, then the next K nodes and so on.
This problem can be solved in 2 ways:
- Using Recursion.
- Without Recursion.
Reverse Linked List in Group of Given size K using Recursion
In each recursion call, we reverse the first K nodes then reverse the next K nodes using recursion. We keep doing this until we reach the end of the Linked List.
We join the K-Group reversed Linked Lists while going back in recursion.
Following illustration shows how it works,

Steps
- Set pointer h = head.
- Reverse the First K nodes of the Linked List using the 3 Pointer method.
- h now points to the last element of the above K size Linked List reversed in the previous step.
- Then Set h->next = reverse(n,k). Here n is the pointer to the K+1 th node in the original Linked List.
- Return the pointer to the Kth node in the original Linked List. This Kth node becomes the first node of the reversed list.
Program to Reverse Linked List in Group of Given Size K
#include<stdio.h> #include<stdlib.h> struct node{ int v; struct node *next; }; // head points to first noed of the linkedlist struct node *head; // inserts value at the front of LinkedList head void insertAtBegin(int value){ struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->v = value; if(head==NULL){ temp->next = NULL; head = temp; return; } temp->next = head; head = temp; } // display linkedlist void displayLL(struct node* head){ struct node *temp = head; while(temp!=NULL){ printf("%d->",temp->v); temp = temp->next; } printf("NULL \n\n"); } struct node* reverseLLK(struct node* head, int k) { if(head==NULL||head->next==NULL) return head; struct node* p; //previous struct node* c; //current struct node* n; //next struct node* h; int i = 1; h = head; c = head; p = NULL; n = c->next; while (n != NULL) { c->next = p; p = c; c = n; n = n->next; ++i; if (i == k) break; } c->next = p; h->next = reverseLLK(n, k); return c; } int main(){ for(int i=1;i<=12;++i){ insertAtBegin(i); } printf("LinkedList:\n"); displayLL(head); head = reverseLLK(head,4); printf("LinkedList after Reverse:\n"); displayLL(head); }
Output
LinkedList: 12->11->10->9->8->7->6->5->4->3->2->1->NULL LinkedList after Reverse: 9->10->11->12->5->6->7->8->1->2->3->4->NULL
Time Complexity: O(N)
Space Complexity: O(N)
Reverse Linked List in Group of Given size K without Recursion
In this method, in each iteration, we reverse the first K nodes. In the next iteration, reverse the next K nodes and so on.
Following illustrates how it works,

Steps
- Initialize pointers
n: points to next node
p: points to the previous node
c: points to the current node
temp1: temporary pointer
temp2: points to the last node of previous K-size reversed group
temp3: points to the first node of the reversed list - Set n = head.
- Repeat the following while n!=NULL
- i = 0
- temp1 = n
- c = n
- p = NULL
- n = c.next
- Repeat the following while n!=NULL AND i!=K
- c.next = p
- p = c
- c = n
- n = n.next
- ++i
- c.next = p;
- If temp3==NULL set temp3 = c
- If temp2!=NULL set temp2.next = c
- temp2 = temp1
- Return temp3.
temp3 points to the first node in the reversed Linked List.
#include<stdio.h> #include<stdlib.h> struct node{ int v; struct node *next; }; // head points to first node of the linkedlist struct node *head; // inserts value at the front of LinkedList head void insertAtBegin(int value){ struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->v = value; if(head==NULL){ temp->next = NULL; head = temp; return; } temp->next = head; head = temp; } // display linkedlist void displayLL(struct node* head){ struct node *temp = head; while(temp!=NULL){ printf("%d->",temp->v); temp = temp->next; } printf("NULL \n\n"); } struct node* reverseLLK(struct node* head, int k) { if(head==NULL||head->next==NULL) return head; struct node* p; //previous struct node* c; //current struct node* n; //next struct node *temp1, *temp2, *temp3; temp1 = temp2 = temp3 = NULL; int i; n = head; while(n!=NULL){ // Reversing K-nodes from n (including node n) i = 1; temp1 = n; c = n; p = NULL; n = c->next; while (n != NULL) { c->next = p; p = c; c = n; n = n->next; ++i; if (i == k) break; } c->next = p; // temp 3 store address of first node of K-group reversed list if(temp3==NULL) temp3 = c; // temp2 stores last node of previous reversed K-nodes if(temp2!=NULL) temp2->next = c; temp2 = temp1; } return temp3; } int main(){ for(int i=1;i<=12;++i){ insertAtBegin(i); } printf("LinkedList:\n"); displayLL(head); head = reverseLLK(head,4); printf("LinkedList after Reverse:\n"); displayLL(head); }
Output
LinkedList: 12->11->10->9->8->7->6->5->4->3->2->1->NULL LinkedList after Reverse: 9->10->11->12->5->6->7->8->1->2->3->4->NULL
Time Complexity: O(N)
Space Complexity: O(1)
References
https://en.wikipedia.org/wiki/Linked_list