C++ program to Sort a Linked List Using Merge Sort














































C++ program to Sort a Linked List Using Merge Sort



Program:
#include<iostream>
 
using namespace std;
 
// A structure representing a node of a linked list.
struct node
{
int data;
node *next;
};
 
// A function creating a new node.
node* NewNode(int d)
{
struct node *temp = new node;
temp->data = d;
temp->next = NULL;
// Returning temp as the new node.
return temp;
}
 
// A function adding the given data at the end of the linked list.
node* AddToList(node *tail, int data)
{
struct node *newnode;
newnode = NewNode(data);
 
if(tail == NULL)
{
tail = newnode;
}
// If tail is not null assign newnode to the next of tail.
else
{
tail->next = newnode;
// Shift tail pointer to the added node.
tail = tail->next;
}
 
return tail;
}
 
node* Merge(node* h1, node* h2)
{
node *t1 = new node;
node *t2 = new node;
node *temp = new node;
 
// Return if the first list is empty.
if(h1 == NULL)
return h2;
 
// Return if the Second list is empty.
if(h2 == NULL)
return h1;
 
t1 = h1;
 
// A loop to traverse the second list, to merge the nodes to h1 in sorted way.
while (h2 != NULL)
{
// Taking head node of second list as t2.
t2 = h2;
 
// Shifting second list head to the next.
h2 = h2->next;
t2->next = NULL;
 
// If the data value is lesser than the head of first list add that node at the beginning.
if(h1->data > t2->data)
{
t2->next = h1;
h1 = t2;
t1 = h1;
continue;
}
 
// Traverse the first list.
flag:
if(t1->next == NULL)
{
t1->next = t2;
t1 = t1->next;
}
// Traverse first list until t2->data more than node's data.
else if((t1->next)->data <= t2->data)
{
t1 = t1->next;
goto flag;
}
else
{
// Insert the node as t2->data is lesser than the next node.
temp = t1->next;
t1->next = t2;
t2->next = temp;
}
}
 
// Return the head of new sorted list.
return h1;
}
 
 
// A function implementing Merge Sort on linked list using reference.
void MergeSort(node **head)
{
node *first = new node;
node *second = new node;
node *temp = new node;
first = *head;
temp = *head;
 
// Return if list have less than two nodes.
if(first == NULL || first->next == NULL)
{
return;
}
else
{
// Break the list into two half as first and second as head of list.
while(first->next != NULL)
{
first = first->next;
if(first->next != NULL)
{
temp = temp->next;
first = first->next;
}
}
second = temp->next;
temp->next = NULL;
first = *head;
}
 
// Implementing divide and conquer approach.
MergeSort(&first);
MergeSort(&second);
 
// Merge the two part of the list into a sorted one.      
*head = Merge(first, second);
}
 
int main()
{
int n, i, num;
struct node *head = new node;
struct node *tail = new node;
head = NULL;
tail = NULL;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
 
 
// Create linked list.
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>num;
 
tail = AddToList(tail, num);
if(head == NULL)
head = tail;
}
 
// Send reference of head into MergeSort().
MergeSort(&head);
 
// Printing the sorted data.
cout<<"\nSorted Data ";
 
while(head != NULL) 
{
cout<<".."<<head->data;
head=head->next;
}
return 0;
}
Output:
Enter the number of data element to be sorted: 10
Enter element 1: 3
Enter element 2: 8
Enter element 3: 9
Enter element 4: 4
Enter element 5: 5
Enter element 6: 7
Enter element 7: 6
Enter element 8: 2
Enter element 9: 0
Enter element 10: 1
 
Sorted Data ->0->1->2->3->4->5->6->7->8->9



More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 239 1
C++ program to Sort a Linked List Using Merge Sort 226 1
C++ Program to Implement a Linked List representation of a Binary tree 221 1
C++ Program to Check for balanced parentheses in an expression 146 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 181 1
C++ program to print Indian flag 201 1
C++ program to Convert a multi level linked list to a singly linked list 152 1
C++ program to print right view of a Binary tree using queue 163 1
C++ Program to implement Huffman Coding Compression Algorithm 225 1
C++ Program to Create a Height Balanced Binary Tree 161 1
C++ program to implement Prims algorithm 235 1
C++ Program for BFS Traversal 174 1
C++ Progam to Evaluate a Prefix Expression 167 1
C++ Program to Implement Queue using Linked List 175 1
C++ implementation of Stack using Linked list 173 1
C++ program to find the intersection point of two linked lists 228 1
C++ program to count the inversions in the given array 215 1
C++ program to perform D.N.F sort 227 1
C++ program to print all possible subsets of a String 215 1
C++ program to count the number of ones in a binary representation of a number 229 1
C++ program to print all possible subsets of a set 246 1
C++ program to find the largest word in a String 220 1
C++ Program to print a matrix in Spiral order 229 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 227 1
C limits library 255 1
Program to add two Binary numbers 231 1

Comments