Question:

Sort a linked list in O(n log n) time using constant space complexity.

Thinking:

There are three basic algorithm to sort in n*logn time. They are merge sort, heap sort and quick sort. And I implement the sort method in merge sort. In order to do this, I have to implement the function such as getLength, get the mid node, merge and so on.

Basic idea of merge sort is to divide a list into two lists, and make them sorted then merge them together.

Solution:

//merge
public ListNode sortList(ListNode head) {
    int len = getLength(head);
    if (len == 0)    return null;
    ListNode nhead = mergeSort(head, len);
    addTail(nhead, len);
    return nhead;
}

private ListNode mergeSort(ListNode head, int n) {
    if (n <= 1)
        return head;
    ListNode mid = getNode(head, n/2);
    ListNode nhead = mergeSort(head, n/2);
    ListNode nmid = mergeSort(mid, n - n/2);
    return merge(nhead, nmid, n);
}

private int getLength(ListNode head) {
    int l = 0;

    while (head != null) {
        head = head.next;
        l++;
    }

    return l;
}

private ListNode getNode(ListNode head, int index) {
    while (index > 0) {
        head = head.next;
        index--;
    }

    return head;
}

private ListNode merge(ListNode p1, ListNode p2, int len) {
    ListNode dummy = new ListNode(0);
    ListNode p = dummy;
    int l1 = 0;
    int l2 = 0;
    while (l1 < len/2 && l2 < len - len/2) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
            p = p.next;
            l1++;
        } else {
            p.next = p2;
            p2 = p2.next;
            p = p.next;
            l2++;
        }
    }
    if (l1 == len/2) {
        p.next = p2;
    } else {
        p.next = p1;
    }
    return dummy.next;
}

private void addTail(ListNode head, int n) {
    while (n > 1) {
        head = head.next;
        n--;
    }
    head.next = null;
}

More efficient method:
Reference:https://leetcode.com/discuss/1709/have-pretty-mergesort-method-anyone-speed-reduce-memory-usage

It use the fast pointer and slow pointer to find the middle index of the linked list. Add a null to the first half to implement the merge operation.

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode f = head.next.next;
    ListNode p = head;
    while (f != null && f.next != null) {
        p = p.next;
        f =  f.next.next;
    }
    ListNode h2 = sortList(p.next);
    p.next = null;
    return merge(sortList(head), h2);
}
public ListNode merge(ListNode h1, ListNode h2) {
    ListNode hn = new ListNode(Integer.MIN_VALUE);
    ListNode c = hn;
    while (h1 != null && h2 != null) {
        if (h1.val < h2.val) {
            c.next = h1;
            h1 = h1.next;
        }
        else {
            c.next = h2;
            h2 = h2.next;
        }
        c = c.next;
    }
    if (h1 != null)
        c.next = h1;
    if (h2 != null)
        c.next = h2;
    return hn.next;
}