Sort List
mediumTime: O(n log n)Space: O(log n)
Signals to notice
sort a linked list in O(n log n)merge sort natural for listsno random access needed
Brute force first
Convert to array, sort, rebuild — O(n log n) but O(n) space.
The key insight
Merge sort: split at middle (slow/fast), sort each half recursively, merge sorted halves. O(n log n) time, O(log n) stack space.
What must stay true
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.
Easy way to go wrong
Using quicksort — it needs random access for efficient partitioning, which lists lack. Merge sort's sequential access is ideal.