# 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: ```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;
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: 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;

};

{

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

{

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;
}

}

int main()
{

int n;
cin>>n;
int data;

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

}
cout<<"before sorting:"<<endl;

cout<<"after sorting:"<<endl;

}
```

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

1. Tilak says: