> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/singly-linked-list/sort-list.md).

# Sort List

## Question ([LC.148](https://leetcode.com/problems/sort-list/))

> 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

```java
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.