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

One response to “Sort a linked list using recursion in C++”

  1. Tilak says:

    In mysort(head,p2,p2->next)
    I think this must wrong because on first comparison the smallest value is swapped at first position so we need to check for next value of list.
    That’s why this is right way of sorting mysort(head,p1->next,p2->next);

Leave a Reply

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