# Bubble Sort On Linked List

Bubble Sort On Linked List” is one of the basic problem based on the linked list data structure and sorting algorithm. Here, we are given a linked list and our task is sort the elements of given linked list in ascending order using bubble sort.

Example:

```Linked List Before Sorting:
Linked List: 19 -> 17 -> 15 -> 18 -> 16
Linked List: 15 -> 16 -> 17 -> 18 -> 19```

#### C++ Program to perform bubble sort on linked listis as follows:

```/* C++ Program to perform bubble sort on linked list */
#include<iostream>
using namespace std;

/* Structure of Node of the Linked List */
struct node
{
int data;
struct node *next;
};

/* Function to Insert Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
/* Creating a Node */
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;

/* Check whether the linked list is empty or not */

/* If Linked List is empty, then new node will become head of the linked list */
{
return;
}

/* If Linked List is not empty, then traverse the complete linked list and point the
pointer of last node of the linked list to the new node of the linked list */
struct node *temp = NULL;
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}

/* Function to Sort the Linked List using Bubble Sort */
{
struct node *temp1;
struct node *temp2;
{
for(temp2 = temp1->next; temp2!=NULL; temp2=temp2->next)
{
if(temp1->data > temp2->data)
{
int temp = temp1->data;
temp1->data = temp2->data;
temp2->data = temp;
}
}
}
}

/* Function to Print the Linked List */
{
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
int main()
{
/* Inserting Some Nodes of the Linked List */
cout<<"The linked list elements before sorting:\n";
cout<<"\n The linked list elements after sorting:\n";
```OUTPUT: