How to Reverse Linked List in Groups of Given Size

Hi there, fellow geeks! In this article, let’s discuss the topic on how to reverse 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.
4. Link the returned node to head (as head will become the last node of the reversed linked list group).
5. Return the last node of the (as it will become the head of the reversed group).

Implementation in C:

//C program to reverse 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("NULLn");
}


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 = %dn",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 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:

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