## How to Reverse A Linked List in Groups of Given Size ##### Sayani Joddar
Share 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:

1. Set currNode=head, prevNode=NULL and nextNode=NULL.
2. Repeat while currNode is not NULL.
3. nextNode=currNode->next.
4. currNode->next=prevNode.
5. prevNode=currNode.
6. 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:

1. If there exists only one node in the linked list, return head.
2. Reverse the first k nodes in the list.
3. Call the function and pass the next node as parameter.
5. 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

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

if(nextNode != NULL)
return prevNode;
}

//auxiliary function to create linked list
struct node* createList(int arr[], int n){
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;
//first node
}
else{
temp->next = newNode;
temp = temp->next;
}
}
}

//auxiliary function to display list
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

printf("Given k = %d\n",k);

//input list
printf("Input: ");

//group-wise reversed list
printf("Output: ");
return 0;
}```

#### Implementation in C++:

```//C++ program to reverse a linked list in groups of k nodes
#include <iostream>
#include <vector>
using namespace std;

public:
//structure of nodes
struct node{
int data;
struct node *next;
};

//constructor to initialize object
}

//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;
//first node
}
else{
temp->next = newNode;
temp = temp->next;
}
}
}

//extra member function to retain abstraction of data
void reverse(int k){
}

//member function to reverse the list in groups of k nodes
struct node* reverseGroup(struct node* head, int k) {
//condition for single node

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

if(nextNode != NULL)
return prevNode;
}

//auxiliary member function to display the linked list
void display(){
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

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:

1. Repeat this process until the linked list is empty.
2. Push the first k nodes.
3. Pop a node and link it to the new top node of the stack. Keep doing this till the stack is empty.
4. Link the last popped node to the next node of the list.
5. 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

stack<struct node*>stk; //stack container from stl

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();
}
else{
prev->next = stk.top();
stk.pop();
prev = prev->next;
}
}
}

prev->next = NULL; //last node
}
```

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

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. ##### Sayani Joddar
Share

Get all the latest updates on what’s happening in the tech & startup world, delivered straight to your inbox from us.

## Related Posts ### Merge 2 Sorted Linked Lists (LeetCode Solution)

Hi there, fellow geeks! In this article, let’s discuss how to merge... ##### Sayani Joddar  