Divide & Conquer — Sort List
↗ LeetCode: Sort List · Medium · pattern chapter →
Sort a linked list in O(n log n) time, O(1) extra space (constant beyond recursion stack).
Example 1 — 4→2→1→3 → 1→2→3→4Example 2 — -1→5→3→4→0 → -1→0→3→4→5
Constraints — 0 ≤ n ≤ 5·10⁴. Brute copy-to-array + Arrays.sort breaks the "sort in-place on linked list" constraint. Merge sort with slow/fast midpoint + iterative merge is O(n log n) = 5·10⁵·17 ≈ 10⁷ ops with O(log n) stack — ~1 hour at Facebook feed scale.
Interview timer00:00
Approach 1 — Copy to array, sort, rebuild
O(n log n) time, O(n) space. Rejected by spec.
Approach 2 — Merge sort with fast/slow split (canonical)
Insight. Divide: find middle with fast/slow. Recurse left and right. Merge two sorted lists.
ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return merge(sortList(head), sortList(slow));
}
ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a != null ? a : b;
return dummy.next;
}Complexity — Time O(n log n); Space O(log n) recursion stack.
Approach 3 — Iterative bottom-up merge sort (true O(1) space)
Insight from top-down. Iterate over merge widths 1, 2, 4, … splitting the list at fixed offsets. No recursion; O(1) extra beyond output.
Complexity — Time O(n log n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Materialize + sort | O(n log n) | O(n) | rejected |
| Recursive merge sort | O(n log n) | O(log n) | canonical |
| Bottom-up merge sort | O(n log n) | O(1) | polish |
When to use which
- Standard interview → recursive top-down.
- True O(1) space required → iterative bottom-up.
- Doubly linked list → merge sort still wins over quicksort due to O(1) split.
Related problems
- Merge Two Sorted Lists — the merge primitive
- Merge k Sorted Lists — extension
- Middle of the Linked List — split primitive