Sort List
mediumTime: O(n log n)Space: O(log n)
Recognize the pattern
sort a linked list in O(n log n)merge sort natural for listsno random access needed
Brute force idea
Convert to array, sort, rebuild — O(n log n) but O(n) space.
Better approach
Merge sort: split at middle (slow/fast), sort each half recursively, merge sorted halves. O(n log n) time, O(log n) stack space.
Key invariant
Merge sort fits linked lists perfectly — merging two sorted lists is O(n) with O(1) extra space, and splitting at the middle uses slow/fast pointers.
Watch out for
Using quicksort — it needs random access for efficient partitioning, which lists lack. Merge sort's sequential access is ideal.