128 lines
3.0 KiB
Java
128 lines
3.0 KiB
Java
|
//This is a java to sort numbers of Linked List using Merge Sort
|
||
|
import java.util.Random;
|
||
|
|
||
|
class Node
|
||
|
{
|
||
|
public int item;
|
||
|
public Node next;
|
||
|
|
||
|
public Node(int val)
|
||
|
{
|
||
|
item = val;
|
||
|
}
|
||
|
|
||
|
public Node()
|
||
|
{}
|
||
|
|
||
|
public void displayNode()
|
||
|
{
|
||
|
System.out.print("[" + item + "] ");
|
||
|
}
|
||
|
}
|
||
|
|
||
|
class LinkedList
|
||
|
{
|
||
|
private Node first;
|
||
|
|
||
|
public LinkedList()
|
||
|
{
|
||
|
first = null;
|
||
|
}
|
||
|
|
||
|
public boolean isEmpty()
|
||
|
{
|
||
|
return (first == null);
|
||
|
}
|
||
|
|
||
|
public void insert(int val)
|
||
|
{
|
||
|
Node newNode = new Node(val);
|
||
|
newNode.next = first;
|
||
|
first = newNode;
|
||
|
}
|
||
|
|
||
|
public void append(Node result)
|
||
|
{
|
||
|
first = result;
|
||
|
}
|
||
|
|
||
|
public void display()
|
||
|
{
|
||
|
Node current = first;
|
||
|
while (current != null)
|
||
|
{
|
||
|
current.displayNode();
|
||
|
current = current.next;
|
||
|
}
|
||
|
System.out.println("");
|
||
|
}
|
||
|
|
||
|
public Node extractFirst()
|
||
|
{
|
||
|
return first;
|
||
|
}
|
||
|
|
||
|
public Node MergeSort(Node headOriginal)
|
||
|
{
|
||
|
if (headOriginal == null || headOriginal.next == null)
|
||
|
return headOriginal;
|
||
|
Node a = headOriginal;
|
||
|
Node b = headOriginal.next;
|
||
|
while ((b != null) && (b.next != null))
|
||
|
{
|
||
|
headOriginal = headOriginal.next;
|
||
|
b = (b.next).next;
|
||
|
}
|
||
|
b = headOriginal.next;
|
||
|
headOriginal.next = null;
|
||
|
return merge(MergeSort(a), MergeSort(b));
|
||
|
}
|
||
|
|
||
|
public Node merge(Node a, Node b)
|
||
|
{
|
||
|
Node temp = new Node();
|
||
|
Node head = temp;
|
||
|
Node c = head;
|
||
|
while ((a != null) && (b != null))
|
||
|
{
|
||
|
if (a.item <= b.item)
|
||
|
{
|
||
|
c.next = a;
|
||
|
c = a;
|
||
|
a = a.next;
|
||
|
}
|
||
|
else
|
||
|
{
|
||
|
c.next = b;
|
||
|
c = b;
|
||
|
b = b.next;
|
||
|
}
|
||
|
}
|
||
|
c.next = (a == null) ? b : a;
|
||
|
return head.next;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
class Merge_Sort
|
||
|
{
|
||
|
public static void main(String[] args)
|
||
|
{
|
||
|
LinkedList object = new LinkedList();
|
||
|
Random random = new Random();
|
||
|
int N = 20;
|
||
|
for (int i = 0; i < N; i++)
|
||
|
object.insert(Math.abs(random.nextInt(100)));
|
||
|
System.out.println("List items before sorting :");
|
||
|
object.display();
|
||
|
object.append(object.MergeSort(object.extractFirst()));
|
||
|
System.out.println("List items after sorting :");
|
||
|
object.display();
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
|
||
|
List items before sorting :
|
||
|
[41] [11] [6] [13] [41] [62] [26] [46] [71] [16] [52] [57] [23] [81] [25] [4] [20] [75] [68] [51]
|
||
|
List items after sorting :
|
||
|
[4] [6] [11] [13] [16] [20] [23] [25] [26] [41] [41] [46] [51] [52] [57] [62] [68] [71] [75] [81]
|