Sort List
Sort a singly linked list in O(n log n) time with merge sort: split at the middle using slow and fast pointers, sort each half, and merge.
Problem Understanding
Sort List: given the head of a linked list, return the list sorted in ascending order. The follow-up asks for O(n log n) time and O(1) memory.
Examples: [4,2,1,3] → [1,2,3,4]; [-1,5,3,4,0] → [-1,0,3,4,5]; [] → [].
The Intuition: Split, Sort, Merge
Copying into an array, sorting and relinking works but uses O(n) memory. Merge sort works on the list directly:
- Split at the middle, found with the slow and fast pointers from Middle of the Linked List.
- Sort each half the same way, down to single nodes.
- Merge the two sorted halves exactly as in Merge Two Sorted Lists.
There are log n levels of halving and each level does O(n) merging work, so the total is O(n log n). See Merge Sort for the same idea on arrays.
Interactive Walkthrough
EACH BOX IS ONE PIECE OF THE LIST · TINTED = SORTED
WHOLE LIST
→
→
→
→
pieces
1
depth
:
Sort [-1, 5, 3, 4, 0] by splitting it in half, sorting each half, and merging
Next
slow and fast find the middle of [-1, 5, 3, 4, 0]: cut after 3 into [-1, 5, 3] and [4, 0]
head
Legend & Complexity
The piece being split, or the left head in a merge
The right head in a merge
A sorted piece, or the merged output so far
The sorted list
Time
O(n log n)
Space
O(log n) stack
Each box is one piece of the list as it exists at that step. Splits cut a box in two; merges join two sorted neighbours, showing the two halves with their heads compared and the merged output above them.
Dry Run Table
Input: [4,2,1,3].
| Step | Pieces |
|---|---|
| split | [4,2] [1,3] |
| split | [4] [2] [1,3] |
| merge 4, 2 | [2,4] [1,3] |
| split | [2,4] [1] [3] |
| merge 1, 3 | [2,4] [1,3] |
| merge: take 1, 2, 3, then link 4 | [1,2,3,4] |
Answer: [1,2,3,4].
The Solution Template
Base case, split with slow and fast, recurse, merge with a dummy head.
Sort List Code
1var sortList = function(head) {2 if (!head || !head.next) return head;3 let slow = head, fast = head.next;4 while (fast && fast.next) {5 slow = slow.next;6 fast = fast.next.next;7 }8 const mid = slow.next;9 slow.next = null;10 let left = sortList(head), right = sortList(mid);11 const dummy = new ListNode();12 let tail = dummy;13 while (left && right) {14 if (left.val <= right.val) { tail.next = left; left = left.next; }15 else { tail.next = right; right = right.next; }16 tail = tail.next;17 }18 tail.next = left || right;19 return dummy.next;20};
Edge Cases & Common Mistakes
- Forgetting to cut: set
slow.next = null, or both halves still reach the end and the recursion never stops. - fast starting at head: a two-node list never splits; start fast at
head.next. - Empty or single-node list: the base case returns it as is.
- Stability: take from the left half on ties (
<=) so equal values keep their order. - Space: the recursion uses O(log n) stack; bottom-up merge sort meets the O(1) follow-up.
Summary
Return lists of 0 or 1 nodes. Otherwise find the middle with slow and fast, cut, sort both halves, and merge them with a dummy head. O(n log n) time, O(log n) stack.
More practice: DSA interview questions with answers · patterns cheat sheet