Linked Lists Sort using Merge Sort
Write a program to sort link list using Merge Sort
Solution:
using System;
namespace LinkedListOpearation
{
class Program
{
public static void Main()
{
var linkedList = new LinkedList();
linkedList.Add(15);
linkedList.Add(10);
linkedList.Add(5);
linkedList.Add(20);
linkedList.Add(3);
linkedList.Add(2);
linkedList.Head = linkedList.MergeSort(linkedList.Head);
Console.WriteLine("Sorted Linked List is:");
linkedList.Print(linkedList.Head);
Console.ReadLine();
}
}
public class LinkedList
{
public Node Head;
public Node SortedMerge(Node node1, Node node2)
{
Node result;
if (node1 == null)
return node2;
if (node2 == null)
return node1;
if (node1.Data <= node2.Data)
{
result = node1;
result.Next = SortedMerge(node1.Next, node2);
}
else
{
result = node2;
result.Next = SortedMerge(node1, node2.Next);
}
return result;
}
public Node MergeSort(Node node)
{
if (node?.Next == null)
{
return node;
}
var intermediate = GetIntermediate(node);
var next = intermediate.Next;
intermediate.Next = null;
var left = MergeSort(node);
var right = MergeSort(next);
return SortedMerge(left, right);
}
public Node GetIntermediate(Node node)
{
if (node == null)
return null;
var currentNode = node.Next;
var nextNode = node;
while (currentNode != null)
{
currentNode = currentNode.Next;
if (currentNode == null) continue;
nextNode = nextNode.Next;
currentNode = currentNode.Next;
}
return nextNode;
}
public void Add(int data)
{
var node = new Node(data) {Next = Head};
Head = node;
}
public void Print(Node head)
{
while (head != null)
{
Console.WriteLine(head.Data);
head = head.Next;
}
}
}
public class Node
{
public int Data;
public Node Next;
public Node(int data)
{
Data = data;
}
}
}