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

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