// -------- START --------

    // Below function is for sort linkedlist using InsertionSort
    
    public static SinglyLinkedListNode sortLinkedList(SinglyLinkedListNode head) {
        
        SinglyLinkedListNode sortedListHead = null; 
        SinglyLinkedListNode current = head; 

        // Traverse the given linked list and insert every node to "sortedListHead"
        
        while (current != null)  
        { 
            // Store next for next iteration 
            SinglyLinkedListNode next = current.next; 
            // insert current in sorted linked list 
            sortedListHead = insertTheNode(sortedListHead, current); 
            // Update current 
            current = next; 
        }
        
        // return 'sortedListHead" node
        
        return sortedListHead;
    }


    // Below function is to insert "nodeTobeInsert" node to "sortedListHead" linkedlist
    
    public static SinglyLinkedListNode insertTheNode(
            SinglyLinkedListNode sortedListHead, SinglyLinkedListNode nodeTobeInsert) {
        
        // Special case for the head end
        if (sortedListHead == null || sortedListHead.data >= nodeTobeInsert.data)  
        { 
            nodeTobeInsert.next = sortedListHead;
            sortedListHead = nodeTobeInsert; 
        } 
        else 
        { 
            SinglyLinkedListNode current = sortedListHead; 

            // Locate the node before the point of insertion
            
            while (current.next != null && current.next.data < nodeTobeInsert.data)  
            { 
                current = current.next; 
            } 
            nodeTobeInsert.next = current.next; 
            current.next = nodeTobeInsert;
        }
        
        return sortedListHead;
    }
    
    // -------- END --------

// -------- START --------

    // Below function is for sort linkedlist using MergeSort
    
    public static SinglyLinkedListNode sortLinkedList(SinglyLinkedListNode head) {
        
        // If head is Null or there is only one element in the linkedlist then return.
        
        if(head == null || head.next == null) {
            return head;
        }
        
        // Get the middle element of linkedlist.
        
        SinglyLinkedListNode middleListNode = getMiddleNode(head);
        SinglyLinkedListNode nextMiddleListNode = middleListNode.next;
        
        /* To devide linkedlist into two halves, put a Null after the middle element.
           So, here "head" pointer points to head of left unsorted linkedlist and 
           "nextMiddleListNode" points to head of right unsorted linkedlist. */
        
        middleListNode.next = null;
        
        // Sorting two halves (left and right).
        // Merge Sort on left linkedlist
        SinglyLinkedListNode leftSortedListNode = sortLinkedList(head);
        
        // Merge Sort on right linkedlist
        SinglyLinkedListNode rightSortedListNode = sortLinkedList(nextMiddleListNode);
        
        // Merging the sorted linkedlist.
        return mergeTwoSortedLists(leftSortedListNode, rightSortedListNode);
        
    }
    
    
    // Below function is to merge sorted linkedlist
    
    public static SinglyLinkedListNode mergeTwoSortedLists(SinglyLinkedListNode a, SinglyLinkedListNode b) {
        
        // If any one linkedlist is null then return other one (Base cases).
        
        if(a == null)
            return b;
        
        if(b == null)
            return a;
        
        // A node to be return, after merging both the sorted linkedlist.
        
        SinglyLinkedListNode headOfMergedList = null, tmpNodeForMergedList = null;
        
        // To keep address of headOfMergedList which is going to be return as head of merged list
        
        if(a.data <= b.data) {
            headOfMergedList = a;
            a = a.next;
        } else {
            headOfMergedList = b;
            b = b.next;
        }
        
        // "tmpNodeForMergedList" points to the end of the linkedlist "headOfMergedList".
        tmpNodeForMergedList = headOfMergedList;
        
        /* We are comparing the top value of linkedlist "a" and linkedlist "b".  
         * Smaller value node will assign to the end of linkedlist "headOfMergedList".
         * We do this until "a" or "b" ends.  
         */
        
        while(a!=null && b!=null) {
            
            if(a.data <= b.data) {
                tmpNodeForMergedList.next = a;
                a = a.next;
                tmpNodeForMergedList = tmpNodeForMergedList.next;
                tmpNodeForMergedList.next = null;
            } else {
                tmpNodeForMergedList.next = b;
                b = b.next;
                tmpNodeForMergedList = tmpNodeForMergedList.next;
                tmpNodeForMergedList.next = null;
            }
            
        }
        
        /* if "b" ends then we assign all remain elements of "a" to end of "headOfMergedList",
         * if "a" ends then we assign all remain elements of "b" to end of "headOfMergedList".
         * and then returns the "headOfMergedList".
         */
        
        if(a!=null) {
            tmpNodeForMergedList.next = a;
        }
        
        if(b!=null) {
            tmpNodeForMergedList.next = b;
        }
        
        return headOfMergedList;
    }
    
    // Below function is to get middle element of the list
    
    public static SinglyLinkedListNode getMiddleNode(SinglyLinkedListNode node) {
        
        if(node == null)
            return node;
        
        SinglyLinkedListNode slowNodePtr = node, fastNodePtr = node.next;
        
        // Move faster pointer by two and slower pointer by one.
        
        while(fastNodePtr != null) {
            fastNodePtr = fastNodePtr.next;
            
            if(fastNodePtr != null) {
                fastNodePtr = fastNodePtr.next;
                slowNodePtr = slowNodePtr.next;
            }
        }
        
        return slowNodePtr;
    }
    
    // -------- END --------