# Reverse a Linked List in Group of Given size

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:

1. Using Recursion.
2. 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

1. Set pointer h = head.
2. Reverse the First K nodes of the Linked List using the 3 Pointer method.
3. h now points to the last element of the above K size Linked List reversed in the previous step.
4. Then Set h->next = reverse(n,k). Here n is the pointer to the K+1 th node in the original Linked List.
5. 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

// inserts value at the front of LinkedList head
void insertAtBegin(int value){
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = value;
temp->next = NULL;
return;
}
}

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) {

struct node* p;	//previous
struct node* c;	//current
struct node* n;	//next
struct node* h;
int i = 1;
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);
}

}```

#### Output

```LinkedList:
12->11->10->9->8->7->6->5->4->3->2->1->NULL
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

1. 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
2. Set n = head.
3. Repeat the following while n!=NULL
1. i = 0
2. temp1 = n
3. c = n
4. p = NULL
5. n = c.next
6. Repeat the following while n!=NULL AND i!=K
1. c.next = p
2. p = c
3. c = n
4. n = n.next
5. ++i
7. c.next = p;
8. If temp3==NULL set temp3 = c
9. If temp2!=NULL set temp2.next = c
10. temp2 = temp1
4. 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

// inserts value at the front of LinkedList head
void insertAtBegin(int value){
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = value;
temp->next = NULL;
return;
}
}

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) {

struct node* p;	//previous
struct node* c;	//current
struct node* n;	//next
struct node *temp1, *temp2, *temp3;
temp1 = temp2 = temp3 = NULL;
int i;

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);
}

}```

#### Output

```LinkedList:
12->11->10->9->8->7->6->5->4->3->2->1->NULL