Sort a linked list (merge sort)

Sort a linked list in n log n time by cutting it in half at the middle, sorting each half, and merging — merge sort adapted to pointers instead of array slices.

The idea

A list of 0 or 1 nodes is already sorted. Otherwise find its middle with slow/fast pointers, cut the Next link there to make two shorter lists, sort each half the same way, and merge the two sorted halves back together by always taking the smaller front node.

Code

public static ListNode SortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode mid = slow.next; slow.next = null;
    ListNode left = SortList(head), right = SortList(mid);
    return Merge(left, right);
}

static ListNode Merge(ListNode a, ListNode b) {
    var dummy = new ListNode(0); ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a ?? b;
    return dummy.next;
}

Tips

• Starting fast one step ahead of slow splits an even-length list into two equal halves instead of leaving one half one node longer.
• A linked list only gives O(n) access to the k-th node, which is exactly why merge sort — sequential access only — is the usual choice here, unlike quicksort.

In the .NET library

The steps below are drawn as a row of values for clarity, but every "cut" and "merge" is really pointer surgery on the very same nodes — nothing is copied into a separate array.