C++ program to reverse a linked list in groups of given size

program to reverse a linked list in groups of given size in C++

How to reverse a linked list in groups of given size?

In this C++ program to reverse a linked list in groups of given size we first need to partition linked list in groups of given size. Now, when our linked list is partitioned into groups, we need to reverse each group. Now as this process is completed our linked list is reversed into groups of given size.

Further in this article we will see steps and algorithm for doing the things explained above.

 

Steps to write a C++ program to reverse a linked list in groups of given size

S

T

E

P

S

 

  1. Construct nodes and initialize the variables.
  2. Create methods to make list.
  3. Now make a method to reverse a linked list in groups.
  4. In this method if head is found NULL, exit.
  5. Else construct three pointers next, prev and curr.
  6. Initialize next and prev to NULL and curr to head.
  7. Now we store the next pointer into next
    and connect the current pointer to the head of the prev.
  8. And in the reverse list head node of the linked list will come to the tail for this we connect the next node to it’s next pointer

S

T

E

P

S

 

  1. Construct nodes and initialize the variables.
  2. Create methods to make list.
  3. Now make a method to reverse a linked list in groups.
  4. In this method if head is found NULL, exit.
  5. Else construct three pointers next, prev and curr.
  6. Initialize next and prev to NULL and curr to head.
  7. Now we store the next pointer into next
    and connect the current pointer to the head of the prev.
  8. And in the reverse list head node of the linked list will come to the tail for this we connect the next node to it’s next pointer

How we can construct a linked list?

Syntax

class Node  

    int data; 
    Node *next; 
}; 

Using following set of codes in our program we can construct linked list.

C++ program to reverse the linked list in groups of given size

Algorithm to reverse a linked list in groups of given size

A

L

G

O

R

I

T

H

M

To reverse a linked list in groups of given size we can follow the following algorithm

  1. IF HEAD==NULL
  2. RETURN
  3. WHILE (CURR && COUNT < K)
  4. NEXT=CURR->NEXT
  5. CURR->NEXT=PREV
  6. PREV=CURR
  7. CURR=NEXT
  8. COUNT++
  9. END WHILE
  10. HEAD->NEXT=REVERSE(CURR,K)
  11. RETURN PREV

A

L

G

O

R

I

T

H

M

To reverse a linked list in groups of given size we can follow the following algorithm

  1. IF HEAD==NULL
  2. RETURN
  3. WHILE (CURR && COUNT < K)
  4. NEXT=CURR->NEXT
  5. CURR->NEXT=PREV
  6. PREV=CURR
  7. CURR=NEXT
  8. COUNT++
  9. END WHILE
  10. HEAD->NEXT=REVERSE(CURR.K)
  11. RETURN PREV

Program to reverse a linked list in groups of given size in C++

#include <iostream>
using namespace std;
class node
{
    public:
    int data;
    node* next;//defining linked list.

     
    node(int d)//making constructor for nodes
    {
        data = d;
        next = NULL;
    }
};
void insertAtTail(node*&head,int data)//function to insert new element at tail of the list
{
    if(head == NULL){
        head = new node(data);
        return;
    }
    node *tail = head;
    while(tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = new node(data);
}
int buildList(node*&head)//function to build the list.
{
    int n;
    cout<<"Enter the size of list:";
    cin>>n;
    cout<<endl;
    int a=n;
    cout<<"Enter data of the nodes\n";
    while(n--){
        int data;
        cin>>data;
        insertAtTail(head,data);//New element will be inserted at end.
    }
    return a;
}
void printList(node*head)//function to print linked list.
{
    if(head == NULL){
        return;
    }
    cout<<head->data<<" ";
    printList(head->next);
}
struct node* reverse(node* head, int k)//function to reverse linked list in groups
{
	if(head==NULL){
		return NULL;
	}
	struct node* next=NULL;
	struct node* prev=NULL;
	struct node* curr=head;
	int count=0;
	while(curr && count<k){
		
		next=curr->next;
		curr->next=prev;
		prev=curr;
		curr=next;
		count++;
	}
	
	head->next=reverse(curr,k);
	return prev;
}
int main() //main function
{
    int k;
    node* head = NULL;
    
    int n = buildList(head);
    cout<<"Linked list data: ";
    printList(head);
    cout<<"\nEnter the group size: ";
    cin>>k;
    head=reverse(head,k);
    cout<<"\nAfter reversing linked list in groups of given size\n";
    cout<<"Linked list data: ";
    printList(head);//printing new linked list.
}
Output:
Enter the size of list:6

Enter data of the nodes
15
23
85
46
96
25
Linked list data: 15 23 85 46 96 25 
Enter the group size: 3

After reversing linked list in groups of given size
Linked list data: 85 23 15 25 96 46

How to reverse a linked list?

Learn by clicking the button below