CareerCup

public static Node mergeSort(Node head){

        if(head == null || head.next==null) return head;

        Node mid = getMidNode(head);
        Node secondList = mid.next;
        mid.next = null;

        return merge(mergeSort(head),mergeSort(secondList));
    }

    public static Node merge(Node h1 ,Node h2){

        Node result ;
        if(h1==null) return h2;
        if(h2 == null) return h1;

        if (h1.data <= h2.data){ result = h1 ; result.next = merge(h1.next,h2); }
        else{
            result = h2 ;
            result.next = merge(h1,h2.next);
        }

        return result;

    }

    public static Node getMidNode(Node head){

        Node fast,slow;
        fast = slow = head;

        while (fast.next!=null && fast.next.next!=null) {

            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

heapsort

Merge sort is the solution. Since this is a linked list(not a array), we don't need O(N) space. We can simply change the pointers while merging them.

QuickSort can be performed on a linked list the same way as on regular array.
Mergesort is not O(1) space, and heapsort requires random access to items in the array to perform the operations on the heap. A random access operation would take O(n) in a linked list, which would increase the run time to (n^2 log n). Quick sort does not require random access operations, and can be done by just keeping a couple of pointers to the current scan and partition locations.

This can be done using iterative merge-sort. Merging linked lists can be done in place (constant space requirement). And recursion is avoided in the iterative version of merge-sort, by doing a bottom-up merge-sort: first merge each pair of consecutive nodes, then merge each pair of 2 nodes, then each pair of 4 nodes, etc.