Sort List

Question (LC.148)

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

Example

Input: 1->3->2->null
Return: 1->2->3->null

Analysis

Quick sort or merge sort? For arrays, QS is to the go-to choice not because of its amortized nlogn time but because of its constant space guarantee. Here for linked lists, merging two sorted arrays is a constant space operation. We can leverage properties of linked list and write a O(nlogn) time and O(1) space merge sort.

Code

public ListNode sortList(ListNode head) {
    return mergeSortList(head);
}

private ListNode mergeSortList(ListNode start) {
    // base case
    if (start == null || start.next == null) {
        return start;
    }
    // divide n1 -> n2 || n3 -> n4 ||
    //        s     m     s2
    ListNode mid = findMid(start);
    ListNode start2 = mid.next;
    mid.next = null;
    // conquer
    ListNode l1 = mergeSortList(start);
    ListNode l2 = mergeSortList(start2);
    // merge
    return mergeTwoSortedLists(l1, l2);
}

private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    // modifying the head so dummy node 
    ListNode dummy = new ListNode(0);
    ListNode t1 = l1;
    ListNode t2 = l2;
    ListNode current = dummy;
    // merge what they have first
    while (t1 != null && t2 != null) {
        if (t1.val < t2.val) {
            current.next = t1;
            current = current.next;
            t1 = t1.next;
        } else {
            current.next = t2;
            current = current.next;
            t2 = t2.next;
        }
    }
    // splice the rest
    if (t1 != null) {
        current.next = t1;
    }
    if (t2 != null) {
        current.next = t2;
    }
    // return new head
    return dummy.next;
}    

// modified findMid fast = head.next instead of head
// this allows the mid to stop at (len/2 - 1) if len is even
private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Be careful where to start with finding middle. If fast starts from head, then we run into a dilemma for even cases e.g. [4,1]. This recursion will never end because the mid is always 1.

Time & Space Complexity

We didn't use any extra temp space for merging. The recurrence T(n) = T(n/2) + T(n/2) + n produces O(nlogn) runtime.