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