Sort a linked list using merge sort
Here given code implementation process.
// C Program
// Sort a linked list using merge sort
#include <stdio.h>
//for malloc function
#include <stdlib.h>
//Create structure
struct Node
{
int data;
struct Node *next;
};
//Add new node at end of linked list
void insert(struct Node **head, int value)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
node->data = value;
node->next = NULL;
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//find last node
while (temp->next != NULL)
{
temp = temp->next;
}
//add node at last possition
temp->next = node;
}
}
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("Empty linked list");
return;
}
struct Node *temp = head;
printf("\n Linked List :");
while (temp != NULL)
{
printf(" %d", temp->data);
temp = temp->next;
if (temp == head)
{
printf("Loop");
//When loop existing
return;
}
}
}
//This are returning middle node of given linked list
struct Node *find_middle(struct Node *head, struct Node *tail)
{
if (head->next == NULL || head == tail)
{
return head;
}
else
{
//Auxiliary variables
struct Node *low = head;
struct Node *high = head;
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
struct Node *merge_list(struct Node *list1, struct Node *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
struct Node *result = NULL;
struct Node *tail = NULL;
struct Node *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->data < list2->data)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail->next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
struct Node *merge_sort(struct Node *front, struct Node *tail)
{
if (front == NULL || front == tail || front->next == NULL)
{
//When have zero or one node
return front;
}
//Find the relative middle node
struct Node *middle = find_middle(front, tail);
//Get the right side sublist
struct Node *right_nodes = merge_sort(middle->next, tail);
//Separate linked list elements
middle->next = NULL;
//Get the left side sublist
struct Node *left_nodes = merge_sort(front, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
int main()
{
struct Node *head = NULL;
//Create linked list
insert( &head, 9);
insert( &head, 5);
insert( &head, 7);
insert( &head, 11);
insert( &head, 3);
insert( &head, 13);
insert( &head, 4);
insert( &head, 8);
insert( &head, 2);
printf("\n Before Sort ");
display(head);
head = merge_sort(head, NULL);
printf("\n After Sort ");
display(head);
return 0;
}
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
// Java Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
System.out.print("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
System.out.println("Empty Linked List");
}
}
//This are returning middle node of given linked list
public Node find_middle(Node first, Node last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node low = first;
Node high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node result = null;
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
public Node merge_sort(Node first, Node last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node middle = find_middle(first, last);
//Get the right side sublist
Node right_nodes = merge_sort(middle.next, last);
//Separate linked list elements
middle.next = null;
//Get the left side sublist
Node left_nodes = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
public static void main(String[] args)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
System.out.print("\n Before Sort ");
obj.display();
obj.head = obj.merge_sort(obj.head, null);
System.out.print("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
public: int data;
Node * next;
Node(int data)
{
//set node value
this->data = data;
this->next = NULL;
}
};
class MyLinkedList
{
public: Node * head;
Node * tail;
//Class constructors
MyLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
//insert node at last of linke list
void insert(int value)
{
//Create a node
Node * node = new Node(value);
if (this->head == NULL)
{
//When linked list empty add first node
this->head = node;
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list nodes
void display()
{
if (this->head != NULL)
{
cout << "\n Linked List :";
Node * temp = this->head;
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
if (temp == this->head)
{
//avoid loop
return;
}
}
}
else
{
cout << "Empty Linked List";
}
}
//This are returning middle node of given linked list
Node * find_middle(Node * first, Node * last)
{
if (first->next == NULL || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node * low = first;
Node * high = first;
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != last && this->head->next->next != last)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
Node * merge_list(Node * list1, Node * list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
Node * result = NULL;
Node * tail = NULL;
Node * node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->data < list2->data)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail->next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
Node * merge_sort(Node * first, Node * last)
{
if (first == NULL || first == last || first->next == NULL)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node * middle = this->find_middle(first, last);
//Get the right side sublist
Node * right_nodes = this->merge_sort(middle->next, last);
//Separate linked list elements
middle->next = NULL;
//Get the left side sublist
Node * left_nodes = this->merge_sort(first, middle);
//sorted merge in two list
return this->merge_list(left_nodes, right_nodes);
}
};
int main()
{
MyLinkedList obj = MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
cout << "\n Before Sort ";
obj.display();
obj.head = obj.merge_sort(obj.head, NULL);
cout << "\n After Sort ";
obj.display();
return 0;
}
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
//Include namespace system
using System;
// C# Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
Console.Write("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
Console.WriteLine("Empty Linked List");
}
}
//This are returning middle node of given linked list
public Node find_middle(Node first, Node last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node low = first;
Node high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node result = null;
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
public Node merge_sort(Node first, Node last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node middle = find_middle(first, last);
//Get the right side sublist
Node right_nodes = merge_sort(middle.next, last);
//Separate linked list elements
middle.next = null;
//Get the left side sublist
Node left_nodes = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
public static void Main(String[] args)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
Console.Write("\n Before Sort ");
obj.display();
obj.head = obj.merge_sort(obj.head, null);
Console.Write("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
<?php
// Php Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
public $data;
public $next;
function __construct($data)
{
//set node value
$this->data = $data;
$this->next = null;
}
}
class MyLinkedList
{
public $head;
public $tail;
//Class constructors
function __construct()
{
$this->head = null;
$this->tail = null;
}
//insert node at last of linke list
public function insert($value)
{
//Create a node
$node = new Node($value);
if ($this->head == null)
{
//When linked list empty add first node
$this->head = $node;
$this->tail = $node;
}
else
{
//Add new node at end of linked list
$this->tail->next = $node;
$this->tail = $node;
}
}
//Display linked list nodes
public function display()
{
if ($this->head != null)
{
echo "\n Linked List :";
$temp = $this->head;
while ($temp != null)
{
echo " ". $temp->data;
$temp = $temp->next;
if ($temp == $this->head)
{
//avoid loop
return;
}
}
}
else
{
echo "Empty Linked List";
}
}
//This are returning middle node of given linked list
public function find_middle($first, $last)
{
if ($first->next == null || $first == $last)
{
return $first;
}
else
{
//Auxiliary variables
//Get first node of linked list
$low = $first;
$high = $first;
while ($high != null && $high->next != null && $high->next->next != null && $high->next != $last && $this->head->next->next != $last)
{
//visit to next node
$low = $low->next;
//visit to second next node
$high = $high->next->next;
}
//This is middle element
return $low;
}
}
//Merge two sorted list and return its result
public function merge_list($list1, $list2)
{
if ($list1 == null)
{
//When list1 is empty
return $list2;
}
else if ($list2 == null)
{
return $list1;
}
else
{
//Some auxiliary variables
$result = null;
$tail = null;
$node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while ($list1 != null || $list2 != null)
{
if ($list1 != null && $list2 != null)
{
//When both list contain nodes
if ($list1->data < $list2->data)
{
//When first list element are smallest
$node = $list1;
$list1 = $list1->next;
}
else
{
//When second list element are smallest
$node = $list2;
$list2 = $list2->next;
}
}
else if ($list1 != null)
{
//When first list contain element
//Get sublist
$node = $list1;
//Set that list1 empty
$list1 = null;
}
else
{
//When second list contain element
//get sublist
$node = $list2;
$list2 = null;
}
if ($result == null)
{
//When get first node of resultant list
$result = $node;
}
else
{
//Add node at end of resultant list
$tail->next = $node;
}
$tail = $node;
}
return $result;
}
}
//Perform merge sort in given linked list
public function merge_sort($first, $last)
{
if ($first == null || $first == $last || $first->next == null)
{
//When have zero or one node
return $first;
}
//Find the relative middle node
$middle = $this->find_middle($first, $last);
//Get the right side sublist
$right_nodes = $this->merge_sort($middle->next, $last);
//Separate linked list elements
$middle->next = null;
//Get the left side sublist
$left_nodes = $this->merge_sort($first, $middle);
//sorted merge in two list
return $this->merge_list($left_nodes, $right_nodes);
}
}
function main()
{
$obj = new MyLinkedList();
//Create linked list
$obj->insert(9);
$obj->insert(5);
$obj->insert(7);
$obj->insert(11);
$obj->insert(3);
$obj->insert(13);
$obj->insert(4);
$obj->insert(8);
$obj->insert(2);
echo "\n Before Sort ";
$obj->display();
$obj->head = $obj->merge_sort($obj->head, null);
echo "\n After Sort ";
$obj->display();
}
main();
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
// Node Js Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
constructor(data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
//Class constructors
constructor()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
insert(value)
{
//Create a node
var node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
display()
{
if (this.head != null)
{
process.stdout.write("\n Linked List :");
var temp = this.head;
while (temp != null)
{
process.stdout.write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
process.stdout.write("Empty Linked List");
}
}
//This are returning middle node of given linked list
find_middle(first, last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low = first;
var high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && this.head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
merge_list(list1, list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var result = null;
var tail = null;
var node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
merge_sort(first, last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
var middle = this.find_middle(first, last);
//Get the right side sublist
var right_nodes = this.merge_sort(middle.next, last);
//Separate linked list elements
middle.next = null;
//Get the left side sublist
var left_nodes = this.merge_sort(first, middle);
//sorted merge in two list
return this.merge_list(left_nodes, right_nodes);
}
}
function main()
{
var obj = new MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
process.stdout.write("\n Before Sort ");
obj.display();
obj.head = obj.merge_sort(obj.head, null);
process.stdout.write("\n After Sort ");
obj.display();
}
main();
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
# Python 3 Program
# Sort a linked list using merge sort
# Node of LinkedList
class Node :
def __init__(self, data) :
# set node value
self.data = data
self.next = None
class MyLinkedList :
# Class constructors
def __init__(self) :
self.head = None
self.tail = None
# insert node at last of linke list
def insert(self, value) :
# Create a node
node = Node(value)
if (self.head == None) :
# When linked list empty add first node
self.head = node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node
# Display linked list nodes
def display(self) :
if (self.head != None) :
print("\n Linked List :", end = "")
temp = self.head
while (temp != None) :
print(" ", temp.data, end = "")
temp = temp.next
if (temp == self.head) :
# avoid loop
return
else :
print("Empty Linked List", end = "")
# This are returning middle node of given linked list
def find_middle(self, first, last) :
if (first.next == None or first == last) :
return first
else :
# Auxiliary variables
# Get first node of linked list
low = first
high = first
while (high != None and high.next != None and high.next.next != None and high.next != last and self.head.next.next != last) :
# visit to next node
low = low.next
# visit to second next node
high = high.next.next
# This is middle element
return low
# Merge two sorted list and return its result
def merge_list(self, list1, list2) :
if (list1 == None) :
# When list1 is empty
return list2
elif(list2 == None) :
return list1
else :
# Some auxiliary variables
result = None
tail = None
node = None
# Combine list elements in sorted order
# This process takes(m+n) time
# Here m is size of list1
# And n is size of list2
while (list1 != None or list2 != None) :
if (list1 != None and list2 != None) :
# When both list contain nodes
if (list1.data < list2.data) :
# When first list element are smallest
node = list1
list1 = list1.next
else :
# When second list element are smallest
node = list2
list2 = list2.next
elif(list1 != None) :
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = None
else :
# When second list contain element
# get sublist
node = list2
list2 = None
if (result == None) :
# When get first node of resultant list
result = node
else :
# Add node at end of resultant list
tail.next = node
tail = node
return result
# Perform merge sort in given linked list
def merge_sort(self, first, last) :
if (first == None or first == last or first.next == None) :
# When have zero or one node
return first
# Find the relative middle node
middle = self.find_middle(first, last)
# Get the right side sublist
right_nodes = self.merge_sort(middle.next, last)
# Separate linked list elements
middle.next = None
# Get the left side sublist
left_nodes = self.merge_sort(first, middle)
# sorted merge in two list
return self.merge_list(left_nodes, right_nodes)
def main() :
obj = MyLinkedList()
# Create linked list
obj.insert(9)
obj.insert(5)
obj.insert(7)
obj.insert(11)
obj.insert(3)
obj.insert(13)
obj.insert(4)
obj.insert(8)
obj.insert(2)
print("\n Before Sort ", end = "")
obj.display()
obj.head = obj.merge_sort(obj.head, None)
print("\n After Sort ", end = "")
obj.display()
if __name__ == "__main__": main()
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
# Ruby Program
# Sort a linked list using merge sort
# Node of LinkedList
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# set node value
self.data = data
self.next = nil
end
end
class MyLinkedList
# Define the accessor and reader of class MyLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
# Class constructors
def initialize()
self.head = nil
self.tail = nil
end
# insert node at last of linke list
def insert(value)
# Create a node
node = Node.new(value)
if (self.head == nil)
# When linked list empty add first node
self.head = node
self.tail = node
else
# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list nodes
def display()
if (self.head != nil)
print("\n Linked List :")
temp = self.head
while (temp != nil)
print(" ", temp.data)
temp = temp.next
if (temp == self.head)
# avoid loop
return
end
end
else
print("Empty Linked List")
end
end
# This are returning middle node of given linked list
def find_middle(first, last)
if (first.next == nil || first == last)
return first
else
# Auxiliary variables
# Get first node of linked list
low = first
high = first
while (high != nil && high.next != nil && high.next.next != nil && high.next != last && @head.next.next != last)
# visit to next node
low = low.next
# visit to second next node
high = high.next.next
end
# This is middle element
return low
end
end
# Merge two sorted list and return its result
def merge_list(list1, list2)
if (list1 == nil)
# When list1 is empty
return list2
elsif(list2 == nil)
return list1
else
# Some auxiliary variables
result = nil
tail = nil
node = nil
# Combine list elements in sorted order
# This process takes(m+n) time
# Here m is size of list1
# And n is size of list2
while (list1 != nil || list2 != nil)
if (list1 != nil && list2 != nil)
# When both list contain nodes
if (list1.data < list2.data)
# When first list element are smallest
node = list1
list1 = list1.next
else
# When second list element are smallest
node = list2
list2 = list2.next
end
elsif(list1 != nil)
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = nil
else
# When second list contain element
# get sublist
node = list2
list2 = nil
end
if (result == nil)
# When get first node of resultant list
result = node
else
# Add node at end of resultant list
tail.next = node
end
tail = node
end
return result
end
end
# Perform merge sort in given linked list
def merge_sort(first, last)
if (first == nil || first == last || first.next == nil)
# When have zero or one node
return first
end
# Find the relative middle node
middle = self.find_middle(first, last)
# Get the right side sublist
right_nodes = self.merge_sort(middle.next, last)
# Separate linked list elements
middle.next = nil
# Get the left side sublist
left_nodes = self.merge_sort(first, middle)
# sorted merge in two list
return self.merge_list(left_nodes, right_nodes)
end
end
def main()
obj = MyLinkedList.new()
# Create linked list
obj.insert(9)
obj.insert(5)
obj.insert(7)
obj.insert(11)
obj.insert(3)
obj.insert(13)
obj.insert(4)
obj.insert(8)
obj.insert(2)
print("\n Before Sort ")
obj.display()
obj.head = obj.merge_sort(obj.head, nil)
print("\n After Sort ")
obj.display()
end
main()
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
// Scala Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class MyLinkedList(var head: Node,
var tail: Node)
{
//Class constructors
def this()
{
this(null, null);
}
//insert node at last of linke list
def insert(value: Int): Unit = {
//Create a node
var node: Node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
def display(): Unit = {
if (this.head != null)
{
print("\n Linked List :");
var temp: Node = this.head;
while (temp != null)
{
print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
print("Empty Linked List");
}
}
//This are returning middle node of given linked list
def find_middle(first: Node, last: Node): Node = {
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low: Node = first;
var high: Node = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
def merge_list(l1: Node, l2: Node): Node =
{
var list1: Node = l1;
var list2: Node = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var result: Node = null;
var tail: Node = null;
var node: Node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
def merge_sort(first: Node, last: Node): Node = {
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
var middle: Node = find_middle(first, last);
//Get the right side sublist
var right_nodes: Node = merge_sort(middle.next, last);
//Separate linked list elements
middle.next = null;
//Get the left side sublist
var left_nodes: Node = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyLinkedList = new MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
print("\n Before Sort ");
obj.display();
obj.head = obj.merge_sort(obj.head, null);
print("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
// Swift Program
// Sort a linked list using merge sort
//Node of LinkedList
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.next = nil;
}
}
class MyLinkedList
{
var head: Node? ;
var tail: Node? ;
//Class constructors
init()
{
self.head = nil;
self.tail = nil;
}
//insert node at last of linke list
func insert(_ value: Int)
{
//Create a node
let node: Node? = Node(value);
if (self.head == nil)
{
//When linked list empty add first node
self.head = node;
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list nodes
func display()
{
if (self.head != nil)
{
print("\n Linked List :", terminator: "");
var temp: Node? = self.head;
while (temp != nil)
{
print(" ", temp!.data, terminator: "");
temp = temp!.next;
}
}
else
{
print("Empty Linked List", terminator: "");
}
}
//This are returning middle node of given linked list
func find_middle(_ first: Node? , _ last : Node? ) -> Node?
{
if (first!.next == nil || first === last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low: Node? = first;
var high: Node? = first;
while (high != nil && high!.next != nil && high!.next!.next != nil && !(high!.next === last) && !(self.head!.next!.next === last))
{
//visit to next node
low = low!.next;
//visit to second next node
high = high!.next!.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
func merge_list(_ l1: Node? , _ l2 : Node? ) -> Node?
{
var list1: Node? = l1;
var list2: Node? = l2;
if (list1 == nil)
{
//When list1 is empty
return list2;
}
else if (list2 == nil)
{
return list1;
}
else
{
//Some auxiliary variables
var result: Node? = nil;
var tail: Node? = nil;
var node: Node? = nil;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != nil || list2 != nil)
{
if (list1 != nil && list2 != nil)
{
//When both list contain nodes
if (list1!.data < list2!.data)
{
//When first list element are smallest
node = list1;
list1 = list1!.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2!.next;
}
}
else if (list1 != nil)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = nil;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = nil;
}
if (result == nil)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail!.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
func merge_sort(_ first: Node? , _ last : Node? ) -> Node?
{
if (first == nil || first === last || first!.next == nil)
{
//When have zero or one node
return first;
}
//Find the relative middle node
let middle: Node? = self.find_middle(first, last);
//Get the right side sublist
let right_nodes: Node? = self.merge_sort(middle!.next, last);
//Separate linked list elements
middle!.next = nil;
//Get the left side sublist
let left_nodes: Node? = self.merge_sort(first, middle);
//sorted merge in two list
return self.merge_list(left_nodes, right_nodes);
}
}
func main()
{
let obj: MyLinkedList = MyLinkedList();
//Create linked list
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
print("\n Before Sort ", terminator: "");
obj.display();
obj.head = obj.merge_sort(obj.head, nil);
print("\n After Sort ", terminator: "");
obj.display();
}
main();
Output
Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment