This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Monday, 8 June 2015

Sort a Linkedlist using merge sort in java


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();
  }
 }
}



No comments:

Post a Comment