Hi there, fellow geeks! In this article, let’s discuss the topic on how to reverse a linked list data structure in groups of a given size.

Given a non-empty single linked list, the goal is to write a function that will reverse a linked list into groups of an integer k.

Suppose the given linked list is,

And k = 3. Then the output linked list should be,

This problem is a modification of the classic linked list reversal problem. It will be solved using the general linked list reversal method.

We assume a linked list consisting of non-zero number of nodes is given as input. Head points to the first node of the linked list. Each node consists of a data field and a next pointer that points to the next node in the list. The general reversal algorithm will change the next pointer of the current node to point to the previous node.

*Algorithm for general reversal:*

- Set currNode=head, prevNode=NULL and nextNode=NULL.
- Repeat while currNode is not NULL.
- nextNode=currNode->next.
- currNode->next=prevNode.
- prevNode=currNode.
- currNode=nextNode.

### Using Recursion

The best method to solve this problem is using a recursive algorithm. We iterate the list in parts, each part consisting of k number of nodes. Each group of k nodes will be reversed according to the above mentioned general linked list reversal algorithm. A loop control will be used to make sure that only k number of nodes are reversed at a time. This algorithm uses a top-down recursion approach.

*Algorithm for reversing a linked list in groups of k nodes:*

- If there exists only one node in the linked list, return head.
- Reverse the first k nodes in the list.
- Call the function and pass the next node as parameter.
- Link the returned node to head (as head will become the last node of the reversed linked list group).
- Return the last node of the (as it will become the head of the reversed group).

#### Implementation in C:

//C program to reverse a linked list in groups of k nodes #include <stdio.h> #include <stdlib.h> //structure of nodes struct node{ int data; struct node *next; }; //recursive function to reverse linked list in groups of k nodes struct node* reverse(struct node* head, int k) { //condition for single node if(head->next == NULL) return head; struct node *currNode = head; struct node *prevNode = NULL; struct node *nextNode = NULL; int c = k; //loop control to reverse the first k nodes while(c-- && currNode != NULL){ nextNode = currNode->next; currNode->next = prevNode; prevNode = currNode; currNode = nextNode; } //condition to link the nodes if(nextNode != NULL) head->next = reverse(nextNode, k); return prevNode; } //auxiliary function to create linked list struct node* createList(int arr[], int n){ struct node *head = NULL,*temp; for(int i=0;i<n;i++){ //creating a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode->data = arr[i]; newNode->next = NULL; if(head == NULL){ //first node head = temp = newNode; } else{ temp->next = newNode; temp = temp->next; } } return head; } //auxiliary function to display list void display(struct node *head){ struct node *temp = head; while(temp != NULL){ printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } int main(){ //using array to insert elements into linked list int arr[] = {7,6,5,4,3,2,1}; int n = sizeof(arr) / sizeof(int); int k = 3; //number of elements in each group struct node *head = createList(arr,n); printf("Given k = %d\n",k); //input list printf("Input: "); display(head); head = reverse(head,k); //group-wise reversed list printf("Output: "); display(head); return 0; }

#### Implementation in C++:

//C++ program to reverse a linked list in groups of k nodes #include <iostream> #include <vector> using namespace std; //class for linked list class LinkedList{ public: //structure of nodes struct node{ int data; struct node *next; }; //head pointer for linked list struct node *head; //constructor to initialize object LinkedList(){ head = NULL; } //auxiliary member function to create list void createList(vector<int> &vec){ int n = vec.size(); struct node *temp; for(int i = 0; i < n; i++){ //creating a new node struct node *newNode = new struct node; newNode->data = vec[i]; newNode->next = NULL; if(head == NULL){ //first node head = temp = newNode; } else{ temp->next = newNode; temp = temp->next; } } } //extra member function to retain abstraction of data void reverse(int k){ head = reverseGroup(head, k); } //member function to reverse the list in groups of k nodes struct node* reverseGroup(struct node* head, int k) { //condition for single node if(head->next == NULL) return head; struct node *currNode = head; struct node *prevNode = NULL; struct node *nextNode = NULL; int c = k; // to keep track of nodes //loop control to reverse k nodes while(c-- && currNode != NULL){ nextNode = currNode->next; currNode->next = prevNode; prevNode = currNode; currNode = nextNode; } //condition to link the nodes if(nextNode != NULL) head->next = reverseGroup(nextNode, k); return prevNode; } //auxiliary member function to display the linked list void display(){ struct node *temp = head; while(temp != NULL){ cout<<temp->data<<" -> "; temp = temp->next; } cout<<"NULL"<<endl; } }; int main(){ //using vector to insert elements into linked list vector<int>vec; for(int i = 7; i > 0; i--){ vec.push_back(i); } int k = 3; //number of elements in each group //object of linked list class LinkedList list; list.createList(vec); //input list cout<<"Given k = "<<k<<endl; cout<<"Input: "; list.display(); //function call to reverse the list list.reverse(k); //group-wise reversed list cout<<"Output: "; list.display(); }

*Complexity Analysis:*

Time complexity of the reverse function is O(n), where ‘n’ is the number of nodes in the linked list. Space complexity of this algorithm is O(n). Please note that system stack is not included in the space complexity for our discussion.

**Using Stack**

When reversal of a linear data structure is asked, stack is usually a good auxiliary container. This question can also be solved as such. Successively pushing and popping reverses the order of elements.

*Algorithm for reversal in groups using stack:*

- Repeat this process until the linked list is empty.
- Push the first k nodes.
- Pop a node and link it to the new top node of the stack. Keep doing this till the stack is empty.
- Link the last popped node to the next node of the list.
- Make the last node to point to NULL.

**Implementation of this algorithm in C++:**

//function to reverse the list in groups of k nodes struct node* reverseGroup(struct node* head, int k) { //condition for single node if(head->next == NULL) return head; stack<struct node*>stk; //stack container from stl struct node *currNode = head; struct node *prev = NULL; while(currNode != NULL){ int c = k; // to keep track of nodes //loop control push k nodes while(c-- && currNode != NULL){ stk.push(currNode); currNode = currNode->next; } //loop control to pop and link the nodes while(!stk.empty()){ if(prev == NULL){ prev = stk.top(); stk.pop(); head = prev; } else{ prev->next = stk.top(); stk.pop(); prev = prev->next; } } } prev->next = NULL; //last node return head; }

*Complexity Analysis:*

Time complexity for this algorithm remains O(n) because each node in the linked list is processed at least once. But an additional space complexity of O(k) is added because of the auxiliary stack.

Also read : **Sliding Window Algorithm**

**Frequently Asked Questions:**

*Q. What are the benefits of using arrays instead of linked lists for this kind of problem?*

Ans. Using array will reduce the space required for pointers because linked list requires pointers to link the nodes, which is not the case for arrays.

*Q. What is the best way to reverse a linked list in groups of given size?*

Ans. Recursion is the best way to reverse a linked list in groups of a given size. But iterating the linked list is also good although it is not very space efficient.

*Q. How do you reverse a linked list of size n?*

Ans. The next pointer of each node of the linked list is made to point to the previous node (or NULL if it is the first node).

**Conclusion**:

It is concluded that a linked list can be reversed in groups of a given size k, if we reverse each group of k nodes separately and link them to each other. We used two methods to solve the problem: a recursive algorithm and an iterative algorithm. Both require O(n) time complexity but the iterative algorithm uses extra space. This problem falls in the category of medium to hard.