Sort List
Problem Statement
Given the head of a linked list, sort the list in ascending order and return the sorted list.
Input
The head of a singly linked list.
Output
The head of the same nodes rearranged into ascending order.
Constraints
- •
0 <= number of nodes <= 5 * 10^4 - •
-10^5 <= Node.val <= 10^5
Examples
Example 1
head = 4 -> 2 -> 1 -> 3
1 -> 2 -> 3 -> 4Example 2
head = -1 -> 5 -> 3 -> 4 -> 0
-1 -> 0 -> 3 -> 4 -> 5Learning Objectives
- Recognise linked-list sorting as a merge-sort problem rather than an array quicksort problem.
- Use fast and slow pointers to split a list into two halves.
- Merge two sorted linked lists with a dummy tail after recursive sorting.
- Explain why bottom-up merge sort removes the recursion stack for **O(1)** auxiliary space.
Intuition
Pattern Recognition
The signal is sort a linked list in O(n log n). Array sorting instincts can be misleading because linked lists do not support random access. Merge sort fits linked lists naturally: splitting only needs fast and slow pointers, and merging only needs next-pointer rewiring.
Top-down merge sort is the clearest interview path. Find the middle, cut the list into two independent halves, recursively sort each half, then reuse the merge-two-sorted-lists routine to stitch them together. The key pointer trap is forgetting to cut slow.next; without that cut, the left recursive call still sees the whole list and never shrinks.
If the interviewer asks for strict O(1) auxiliary space, switch the discussion to bottom-up merge sort. It iteratively merges runs of size 1, then 2, then 4, avoiding recursion while keeping the same merge idea.
Common mistakes
- ×Using array-style random indexing, which is inefficient on linked lists.
- ×Finding the middle but forgetting to set **slow.next** to **null**, causing infinite recursion.
- ×Losing the head of the second half while cutting the list.
- ×Claiming top-down merge sort is **O(1)** space even though the recursion stack is **O(log n)**.
Algorithm Explanation
Key idea
Merge sort works because each split halves the list and each merge rebuilds sorted order using only pointer comparisons. The top-down invariant is: sortList(head) returns a sorted version of exactly the nodes reachable from head after the caller has made that segment finite.
Pointer walkthrough
For 4 -> 2 -> 1 -> 3, start slow at 4 and fast at 2. Move slow to 2 while fast jumps to 3. Since fast.next is now empty, slow marks the end of the left half. Save secondHalf = 1 -> 3, then cut 2.next so the halves become 4 -> 2 and 1 -> 3. Recursively split 4 -> 2 into 4 and 2, merge into 2 -> 4. Split 1 -> 3 into 1 and 3, merge into 1 -> 3. The final merge compares heads 2 and 1, emits 1, then 2, then 3, then 4.
Algorithm
- If the list has zero or one node, return it because it is already sorted.
- Use slow and fast pointers to find the node before the start of the right half.
- Save the right-half head and cut slow.next to separate the two halves.
- Recursively sort the left half and the right half.
- Merge the two sorted halves with the standard dummy-tail two-list merge.
- Return the merged head.
Solutions
Solution 1: Top-down linked-list merge sort
Use this first in interviews because it is concise, clearly uses fast and slow pointers, and mirrors the familiar merge-sort recurrence.
Recursively split the list at the middle, sort both halves, then merge the sorted halves. The split step must physically break the list so each recursive call receives a smaller segment.
Step-by-step
- Return head immediately when the segment has zero or one node.
- Run slow and fast so slow stops just before the right half.
- Store secondHalf = slow.next, then set slow.next = null to cut the segment.
- Recursively sort head and secondHalf.
- Merge the two sorted lists by advancing the smaller head each time.
- Return dummy.next from the merge helper.
O(n log n)
O(log n)
Each level merges all n nodes, and the balanced recursion stack has depth O(log n).
Java implementation
Solution 2: Bottom-up iterative merge sort
Use this as the follow-up when the interviewer asks for O(1) auxiliary space and wants recursion removed.
Count the list length, then merge sorted runs iteratively. First merge runs of size 1, then 2, then 4, doubling until the run size covers the whole list.
Step-by-step
- Count the total number of nodes.
- Attach the list to dummy so each pass can rebuild from a stable head.
- For each run size, walk the list and split out a left run and a right run of that size.
- Merge the two runs after previousTail and return the new tail of the merged run.
- Continue until every run in the pass is merged.
- Double the run size and repeat until the whole list is sorted.
O(n log n)
O(1)
The algorithm uses iterative run sizes and a constant number of pointers, with no recursion stack.
Java implementation
Dry Run
Sample input
head = 4 -> 2 -> 1 -> 3. Track the top-down splits and merges that produce the final sorted list.
| phase | left side | right side | action | result |
|---|---|---|---|---|
| split 4 -> 2 -> 1 -> 3 | 4 -> 2 | 1 -> 3 | slow cuts after 2 | two halves |
| split 4 -> 2 | 4 | 2 | cut into single nodes | ready to merge |
| merge 4 and 2 | 4 | 2 | take 2 then 4 | 2 -> 4 |
| split 1 -> 3 | 1 | 3 | cut into single nodes | ready to merge |
| merge 1 and 3 | 1 | 3 | take 1 then 3 | 1 -> 3 |
| final merge | 2 -> 4 | 1 -> 3 | take 1, 2, 3, 4 | 1 -> 2 -> 3 -> 4 |
Every split makes smaller finite lists, and every merge consumes two sorted lists. The final merge returns 1 -> 2 -> 3 -> 4.
Interview Tips
Explain why merge sort is preferred for linked lists: it does not need random access, and merging is pointer-friendly. Be precise about the split: fast starts at head.next so slow stops before the right half and can cut the list. For the follow-up, mention bottom-up merge sort as the strict O(1) space version because it replaces recursion with iterative run sizes.
Likely follow-ups
- How would you implement the bottom-up version if recursion depth were not allowed?
- How would you keep the sort stable when equal values appear?
- What changes if the list is doubly linked?
- Could quicksort be a good choice for linked lists, and why is merge sort usually safer?
Similar Problems
Key Takeaways
- Linked-list sorting naturally points to merge sort because splitting and merging are pointer operations.
- Cutting the list at the middle is mandatory before recursive calls.
- Top-down merge sort uses **O(log n)** stack space; bottom-up merge sort can reach **O(1)** auxiliary space.
- The merge-two-sorted-lists routine is a reusable linked-list primitive.