package linkedlist.singly;
// Sort a Singly Linkedlist using mergesort
public class SortLinkedList {
Node startNode;
public static void main(String[] args) {
new SortLinkedList();
}
public SortLinkedList() {
Node temp1 = new Node(10);
Node temp2 = new Node(1);
Node temp3 = new Node(2);
Node temp4 = new Node(8);
Node temp5 = new Node(9);
Node temp6 = new Node(10);
Node temp7 = new Node(1);
temp1.setNext(temp2);
temp2.setNext(temp3);
temp3.setNext(temp4);
temp4.setNext(temp5);
temp5.setNext(temp6);
temp6.setNext(temp7);
startNode = temp1;
Node temp = mergeSortLinkList(startNode);
printLinkList(temp);
}
private Node mergeSortLinkList(Node startNode){
//Break the linklist into 2 list first.
//So find middle and then from that point there will be 2 list.
if(startNode==null || startNode.getNext()==null){
return startNode;
}
//Now two list are, FIRST from start to middle and SECOND from middle+1 to last.
Node middle = getMiddle(startNode);
Node nextOfMiddle = middle.getNext();
middle.setNext(null);
Node left = mergeSortLinkList(startNode);
Node right = mergeSortLinkList(nextOfMiddle);
Node sortedList = mergeTwoListRecursive(left, right);
//Node sortedList = mergeTwoListIterative(left, right);
return sortedList;
}
//Recursive Approach for Merging Two Sorted List
private Node mergeTwoListRecursive(Node startNode, Node endNode){
if(startNode==null)
return endNode;
if(endNode==null)
return startNode;
Node temp=null;
if(startNode.getData()<endNode.getData()){
temp=startNode;
temp.setNext(mergeTwoListRecursive(startNode.getNext(), endNode));
}else{
temp=endNode;
temp.setNext(mergeTwoListRecursive(startNode, endNode.getNext()));
}
return temp;
}
//Iterative Approach for Merging Two Sorted List
private Node mergeTwoListIterative(Node left, Node right) {
Node merged=null;
Node temp=null;
//To keep track of last last element, so that we don't need to iterate for adding the element at last of list.
Node last=null;
while(left!=null && right!=null){
if(left.getData()>right.getData()){
temp = new Node(right.getData());
right=right.getNext();
}else{
temp = new Node(left.getData());
left=left.getNext();
}
if(merged==null){
merged=temp;
}else{
last.setNext(temp);
}
last=temp;
}
if(left!=null){
last.setNext(left);
}else{
last.setNext(right);
}
return merged;
}
private Node getMiddle(Node startNode) {
if(startNode==null){
return startNode;
}
Node pointer1=startNode;
Node pointer2=startNode;
while(pointer2!=null && pointer2.getNext()!=null && pointer2.getNext().getNext()!=null){
pointer1 = pointer1.getNext();
pointer2 = pointer2.getNext().getNext();
}
return pointer1;
}
private void printLinkList(Node startNode) {
Node tempNode = startNode;
while(tempNode!=null){
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.getNext();
}
}
}
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Monday, 8 June 2015
Sort a Linkedlist using merge sort in java
Labels:
Sorting
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment