Sort a linked list using recursion in C++

In this tutorial, we will learn how to sort a linked list in C++ using recursion. A Linked list is a data structure. It is made up of nodes that are created using self-referential structures. The class node contains one data member data and the other is a pointer pointing to the next node of type *node.

Input:

8
7 3 4 5 1 2 2 3

Output:

Sort a linked list using recursion in C++

before sorting:
3-->2-->2-->1-->5-->4-->3-->7-->
after sorting:
1-->2-->2-->3-->3-->4-->5-->7-->

How to sort a linked list using recursion in C++

The structure of the class node is as follows:

class node{
public:
    int data;
    node* next;

};

Insertion in a linked list:

The steps are:

  1. We create a new node temp and store the data passed in function in temp->data.
    node *temp=new node();
        temp->data=data;
  2. We store the head in a new node q. and store temp in the head.
  3. Then, we append q in front of temp. q which was primarily our head.
    node *q=head;
    head=temp;
    temp->next=q;

     

Print a linked list:

Create a new node temp and store head in it. While(it is not null), print the data. and change the temp to temp->next.

Algorithm to sort linked list:

  1. Our linked list before sorting is:       3–>2–>2–>1–>5–>4–>3–>7–>
  2. We will pass 3 arguements in function(head,head,head->next) i.e head is 3 and head->next is 2.Let head be p1 and 2 be p2.
  3. We will check if p2 is NULL. It means we have reached our last element and sorting has been done. This is our base case.
  4. Let p3 be p1->next.
  5. while(p3!=NULL)
        {
            if(p1->data>p3->data)
            {
                swap(p1->data,p3->data);
            }
            p3=p3->next;
        }

     

  6. Traverse the elements of the linked list and compare the values and swap accordingly.
  7. After this pass, our linked list will be like this:
    final output linked list
  8. Then, recursively call for the next 2 elements.

C++ code to Sort a linked list using recursion

#include<iostream>
using namespace std;

class node{
public:
    int data;
    node* next;

};

void insertionathead(node *&head,int data)
{

    node *temp=new node();
    temp->data=data;
     node *q=head;
     head=temp;
     temp->next=q;
     return;
}

void display(node *head)
{
    node *temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<"-->";
        temp=temp->next;
    }

     cout<<endl;
}

void mysort(node *&head,node *p1,node *p2)
{
    if(p2==NULL)
    {
        return;
    }

   node *p3=p1->next;
   while(p3!=NULL)
    {
        if(p1->data>p3->data)
        {
            swap(p1->data,p3->data);
        }
        p3=p3->next;
    }

    mysort(head,p2,p2->next);
}


int main()
{
    node *head1=NULL;

    int n;
    cin>>n;
    int data;

    for(int i=0;i<n;i++)
    {
        cin>>data;
        insertionathead(head1,data);


    }
    cout<<"before sorting:"<<endl;
    display(head1);

    mysort(head1,head1,head1->next);
    cout<<"after sorting:"<<endl;
    display(head1);


}

Input:

8
7 3 4 5 1 2 2 3

Output:

before sorting:
3-->2-->2-->1-->5-->4-->3-->7-->
after sorting:
1-->2-->2-->3-->3-->4-->5-->7-->

 

Also, refer to:

Reverse a linked list using STL

Leave a Reply

Your email address will not be published. Required fields are marked *