Sort List

Given the head of a singly linked list, sort it in O(n log n) time and O(1) space. This constraint rules out every comparison sort that swaps in place — the machine cannot index a linked list, so quicksort and heapsort are off the table.

The key insight: merge sort is the natural fit because its merge phase only needs to relink nodes — no random access required. The divide step finds the midpoint with the slow-fast pointer walk; the conquer step merges two already-sorted halves using the dummy-node splice. Recursion costs O(log n) stack space; the iterative bottom-up variant achieves true O(1).

Approach:

1. Split the list at its midpoint; recurse on both halves until singletons.
2. Merge the two sorted halves with the standard two-pointer splice.
3. The recursion unwinds, combining sorted sublists into the full sorted list.

def sort_list(head):
    if not head or not head.next:
        return head
    slow, fast, prev = head, head, None
    while fast and fast.next:
        prev, slow, fast = slow, slow.next, fast.next.next
    prev.next = None
    left, right = sort_list(head), sort_list(slow)
    dummy = tail = ListNode(0)
    while left and right:
        if left.val <= right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

Time: O(n log n). Space: O(log n) recursion depth, or O(1) with bottom-up merging.

Trickiest edge case: two-node lists — prev.next = None must cut before the recursion, or the halves never separate and the machine loops forever.