135. Sort List

Split the list in half with a slow/fast pointer, recursively sort each half, then merge the two sorted halves. Merge sort is ideal for linked lists because splitting and merging only relink pointers — no random access or extra array is needed.

Idea

Merge sort suits linked lists perfectly: you never need random access, and merging two sorted lists is just pointer rewiring. It runs in guaranteed O(n log n).

Three steps: split the list into two halves, recursively sort each, then merge the sorted halves.

Algorithm

1. Base case: an empty or single-node list is already sorted — return it.
2. Split: use slow/fast pointers (fast moves twice as fast) to find the middle; cut the list there into left and right.
3. Recurse: left = sortList(left), right = sortList(right).
4. Merge: walk both sorted lists with a dummy-headed result, always attaching the smaller front node; append whatever remains.

Worked example: 4→2→1→3

• Split → 4→2 and 1→3.
• Sort halves → 2→4 and 1→3.
• Merge: 1 < 2 → 1; 2 < 3 → 2; 3 < 4 → 3; then 4 → 1→2→3→4.

Complexity

• Time: O(n log n) — log n levels of splitting, O(n) merge per level.
• Space: O(log n) recursion stack.

class Solution {
    public 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);
        ListNode right = sortList(mid);
        ListNode dummy = new ListNode(0), tail = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        tail.next = (left != null) ? left : right;
        return dummy.next;
    }
}