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

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

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

  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

Syntax

class Node  

    int data; 
    Node *next; 
}; 
C++ Program to reverse a linked list in groups of given size

Algorithm to reverse a linked list in groups of given size

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

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java