Sort List

Problem

A data pipeline receives events as a linked list that arrives out of order and must be sorted before downstream processing. Sort the linked list in ascending order with O(n log n) time complexity.

Input: 4->2->1->3        -> 1->2->3->4
Input: -1->5->3->4->0    -> -1->0->3->4->5
Input: []                -> []

Solution

Approach: Top-down merge sort on a linked list, using slow/fast pointers to split.

A list of zero or one node is already sorted, so that is the base case that stops the recursion. Otherwise the list is split in half. The slow/fast pointer walk advances slow one node and fast two nodes per step, so when fast runs off the end, slow sits at the start of the second half; prev trails one behind slow so that prev.next = None can sever the list into two independent halves. Severing is what makes this correct - without it the right half would still chain into the left half's tail, producing duplicated nodes and infinite recursion. Each half is sorted recursively, then the two sorted halves are merged with a dummy head: compare the front node of each half, splice the smaller one onto cur, advance that half, and after one half empties, attach the other half's remaining tail wholesale.

Trace [4,2,1,3]: split into [4,2] and [1,3], which split again to single nodes; the merges rebuild [2,4] and [1,3], then the final merge interleaves them into [1,2,3,4]. The merge only rewires existing nodes - no new ListNode is allocated.

Edge cases: Empty list and single node return immediately via the base case. A two-node list 1->2 splits cleanly because prev is set before slow moves. Negative values sort correctly since comparison is by val.

Complexity: O(n log n) time, O(log n) space - log n recursion levels each doing O(n) split-plus-merge work; space is the recursion stack, since merging is O(1) pointer rewiring.