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

Can we do merge sort? We have O(nlogn) time but what about O(1) space? Well Yes! Recall Merge Two Sorted Lists. You need to take advantage of the properties of linked list. You can't just use same approach with indices in arrays. Be careful where to start with finding middle. S&F start from the dummy node. If you start from head, then slow will be at head and fast will be at head.next.

Code

public ListNode sortList(ListNode head) {
    // base case
    if (head == null || head.next == null)
        return head;
    // divide
    // start...mid is the first half, mid.next...end is the second half
    ListNode mid = findMid(head);
    ListNode secondHead = mid.next;
    mid.next = null;
    // conquer
    ListNode list1 = sortList(head);
    ListNode list2 = sortList(secondHead);
    // combine
    return mergeTwoSortedLists(list1, list2);
}

private ListNode findMid(ListNode start) {
    // find mid with fast & slow pointers
    ListNode slow = start, fast = start.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

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.