Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Sort a linked list in O(n log n) time by running merge sort directly on the nodes. Split the list into two halves using the fast/slow pointer trick, recursively sort each half, then merge the two sorted halves with a dummy-node splice. Merge sort is the right choice (not quicksort or heapsort) because it needs only sequential access and merges linked lists in O(1) extra space per merge — exactly what a singly linked list offers. The recursion stack costs O(log n); for true O(1) space, switch to bottom-up merge sort.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know merge sort is the natural O(n log n) sort for linked lists — and can implement the two sub-routines (split by fast/slow, merge by dummy node) cleanly without losing or cycling nodes.
Where candidates slip
Forgetting to cut the list at the midpoint (so the two halves still share nodes and recursion never bottoms out), or reaching for quicksort and getting tangled in pivot partitioning on a singly linked list.
How to stand out
Implement top-down cleanly, then say: 'This is O(log n) stack space; the bottom-up iterative version gets us to O(1) space.' Naming that upgrade signals you understand WHY merge sort wins on lists.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Top-down split-down then merge-up. Each level touches all n nodes; there are log n levels → O(n log n).
How to read it:fast/slow find the midpoint; prev lets us sever the first half so the two sublists are disjoint.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Dump to Array, Sort, Rebuild
1Hint 1Explore hintHide hint
A linked list is hard to sort directly, but an array is trivial — the library sort is O(n log n). Can you move the data into a structure you already know how to sort?
2Hint 2Explore hintHide hint
Walk the list once collecting every value into an array, sort the array, then walk the list a second time overwriting each node's value in sorted order.
3Hint 3Explore hintHide hint
You never touch the `next` pointers — the node structure stays identical, only the `val` fields are rewritten. That's why it's so simple, and also why it costs O(n) extra space.
A · Core idea
This approach sidesteps the hard part of the problem entirely. The difficulty in sorting a linked list comes from the lack of random access — but an array has random access and a battle-tested O(n log n) library sort. So we borrow the array: copy every node's value into a list, sort that list, then walk the original nodes a second time and overwrite each val with the next sorted value.
Why this is worth saying out loud. Interviewers want to see you reduce an unfamiliar problem to a familiar one. 'Sort a linked list' becomes 'sort an array' the moment you decouple the values from the node structure. It's correct, it's fast, and it takes thirty seconds to write — a perfectly good answer if the constraints don't forbid extra space.
Why it doesn't satisfy the follow-up. The whole point of LeetCode 148's follow-up is the phrase O(1) memory. The auxiliary array holds all n values, so this is O(n) space. It also feels like cheating — you're not really sorting the list, you're sorting an array and copying answers back. The interviewer will almost always respond with 'nice, now do it without the extra array', which is your cue to bring out merge sort.
The subtle correctness point. Because we only overwrite val and never re-link nodes, the list's shape is preserved and there's zero risk of creating a cycle or dropping a node. That safety is the upside of trading space for simplicity — but it's exactly that extra array we're asked to eliminate.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
head = [4,2,1,3]collect
walk list pushing each val
vals = [4, 2, 1, 3][1, 2, 3, 4]C · Code with teaching comments
Reference implementation previewpublic ListNode sortList(ListNode head) { List<Integer> vals = new ArrayList<>(); for (ListNode cur = head; cur != null; cur = cur.next) { vals.add(cur.val); }Explore the full codeHide the full code
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Reducing 'sort a linked list' to 'sort an array' is the canonical trick of mapping a hard structure onto an easy one. Always mention it — it proves you can simplify — but be ready for the interviewer to immediately raise the space bar, which forces the real answer.
ComplexityO(n log n) time, O(n) space — Collecting values is O(n), sorting the array is O(n log n), rewriting is O(n) → O(n log n) total. The array of n values is O(n) extra space, which violates the follow-up's O(1) requirement.
E · Edge cases and pitfalls5head = [] — First loop never runs, vals stays empty, sort is a no-op, returns head (null).Explore edge casesHide edge cases
Edge cases handled
head = []First loop never runs, vals stays empty, sort is a no-op, returns head (null).head = [1]Single value collected and rewritten unchanged — already sorted.
Pitfalls
- Claiming this is O(1) space — the auxiliary array is O(n), which fails the follow-up.
- Rebuilding brand-new nodes instead of overwriting val — unnecessary allocation and a chance to drop the tail.
- Forgetting to reset the cursor to head before the second pass.
Approach 2 of 3 · Optimal
Top-Down Merge Sort (Optimal, O(log n) stack)
1Hint 1Explore hintHide hint
Merge sort works by sorting two halves and merging them. You already know how to merge two sorted lists in O(1) space — so the only new piece is splitting a list into two halves.
2Hint 2Explore hintHide hint
Split with the fast/slow pointer trick: advance `fast` two steps and `slow` one step; when `fast` reaches the end, `slow` is at the middle. Keep a `prev` so you can cut the list with `prev.next = null`.
3Hint 3Explore hintHide hint
Recurse on each half, base-casing when the list has 0 or 1 nodes, then merge the two sorted results with a dummy-head splice and return `dummy.next`.
A · Core idea
Merge sort is the textbook divide-and-conquer sort, and a linked list is the structure it was practically designed for. The algorithm is three steps: divide the list into two halves, conquer by recursively sorting each half, and combine by merging the two sorted halves into one. The base case is a list of zero or one node, which is already sorted, so recursion bottoms out there.
Why merge sort and not quicksort or heapsort. A singly linked list only supports sequential, forward access — there's no O(1) 'jump to index k'. Quicksort's partition step wants to swap elements around a pivot, which is painful without random access and degrades to O(n²) on adversarial input. Heapsort needs an array-backed heap. Merge sort, by contrast, only ever walks forward and its merge step splices two sorted lists in O(1) extra space by rewiring next pointers. The structure's one weakness (no random access) simply doesn't matter to merge sort, and its one strength (cheap splicing) is exactly what merge exploits.
The split sub-routine, and why `prev` matters. To divide, we find the midpoint with the fast/slow pointer trick: fast moves two nodes per step, slow moves one, so when fast falls off the end, slow sits at the middle. The critical detail is that finding the middle isn't enough — we must sever the list into two independent lists. We track the node before slow (call it prev) and set prev.next = null. Skip this cut and the 'two halves' still share nodes; the recursion on the second half walks right back into the first half, never shrinks the input, and you get infinite recursion or a stack overflow. The cut is what makes the subproblems strictly smaller.
The merge sub-routine, reused wholesale. Combining is exactly Merge Two Sorted Lists: a dummy head, a tail pointer, and a loop attaching the smaller current node until one list empties, then splicing the remainder in one link. Using a dummy node means the first attachment needs no special case, and returning dummy.next hands back the real head. Using <= in the comparison keeps equal values in their original order, making the whole sort stable.
Putting the cost together. Every level of the recursion does O(n) total work (the merges at that level collectively touch all n nodes), and because each split halves the list, the depth is log n levels — hence O(n log n) time, the optimal comparison-sort bound. The only non-constant space is the recursion stack at depth log n, so this is O(log n) space — close to, but not quite, the follow-up's O(1) target, which the bottom-up variant achieves.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
head = [4,2,1,3]Interactive diagram
Fast/slow split with prev
split [4,2,1,3]When fast hits the end, slow is the midpoint; prev.next=null cuts the list.
[1, 2, 3, 4]C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(log n) spaceOpen the invariant and proofExplore the proofHide the proof
Merge sort on a list is just two reusable primitives glued together: split-by-fast/slow and merge-by-dummy-node. If you can write Middle of the Linked List and Merge Two Sorted Lists, you can write this — the recursion is the trivial part. Recognizing problems as compositions of primitives you already own is how you stay calm under interview pressure.
ComplexityO(n log n) time, O(log n) space — Each recursion level processes all n nodes across its merges (n total work per level), and the list halves each level, so there are log n levels → O(n log n) time. The recursion goes log n deep, so the call stack is O(log n) space; no auxiliary arrays are allocated, only pointers rewired.
E · Edge cases and pitfalls8head = [] — Base case head==null returns null immediately.Explore edge casesHide edge cases
Edge cases handled
head = []Base case head==null returns null immediately.head = [1]head.next==null returns the single node unchanged.head = [2,1]Split into [2] and [1], merge picks 1 then 2 → [1,2]; smallest non-trivial split.head = [3,1,3,2]Duplicate 3s stay in original relative order thanks to <= (stability).
Pitfalls
- Not cutting at the midpoint (omitting prev.next=null) — the halves share nodes and recursion never terminates.
- Using slow=head, fast=head.next mismatched with the prev bookkeeping — pick one convention and keep it consistent.
- Returning dummy instead of dummy.next from merge — dummy is a throwaway sentinel.
- Using < instead of <= — still correct, but loses stability for equal values.
Approach 3 of 3
Bottom-Up Merge Sort (True O(1) Space)
1Hint 1Explore hintHide hint
The recursion stack is the only thing keeping top-down from O(1) space. Can you produce the same merges iteratively, smallest sublists first?
2Hint 2Explore hintHide hint
Merge sublists of size 1 into runs of size 2, then merge size-2 runs into size-4, doubling the run length each outer pass until it exceeds n.
3Hint 3Explore hintHide hint
For each pass, walk the list cutting off two consecutive runs of the current size, merge them, and stitch the result onto a running tail using a dummy head.
A · Core idea
Bottom-up merge sort produces exactly the same merges as top-down but schedules them iteratively, eliminating the recursion stack and hitting the follow-up's O(1) space target. Instead of splitting top-down, we build the sorted result up from the smallest pieces: first treat each node as a sorted run of length 1, merge adjacent runs into runs of length 2, then merge those into runs of length 4, and so on, doubling the run length each outer pass until it covers the whole list.
Why it's O(1) space. There is no recursion, so there is no call stack growing with n, and we allocate no auxiliary array. The algorithm uses a fixed handful of pointers — a dummy head, a tail, and cursors to carve out the two runs being merged — regardless of list size. That's the entire reason this variant exists: it's the only version that truly answers 'O(1) memory'.
The machinery: split off a run, merge, repeat. Each outer pass fixes a size. We sweep the list left to right: detach a run of size nodes (call it left), then detach the next size nodes (right), merge them with the same dummy-node merge from before, and append the merged run to a tail that accumulates the fully-processed prefix. We keep a helper that walks size−1 steps and cuts the link to return the head of what remains. We repeat until the whole list is consumed for this pass, then double size.
Why it produces a sorted list. After the pass with size = 1, every adjacent pair is internally sorted (runs of length ≤ 2). After size = 2, every group of four is sorted, and so on. Each pass maintains the invariant that the list is a sequence of sorted runs of length size (the last run may be shorter), and merging adjacent runs doubles their length while keeping them sorted. Once size >= n, the entire list is one sorted run and we stop.
The honest trade-off. Bottom-up is fiddlier to code correctly under pressure — the split-and-stitch bookkeeping is where bugs hide — so in an interview it's often best to write the clean top-down version first, get it correct, then describe (or implement if asked) the bottom-up upgrade. Stating that you know the O(1) version exists and why it works frequently earns the credit even without flawless on-the-spot code.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
head = [4,2,1,3]size=1
merge [4]&[2]→[2,4], merge [1]&[3]→[1,3]
[2,4,1,3][1, 2, 3, 4]C · Code with teaching comments
Reference implementation previewpublic ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; int n = 0; for (ListNode cur = head; cur != null; cur = cur.next) n++;Explore the full codeHide the full code
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Top-down vs bottom-up is the recursion-vs-iteration duality applied to divide-and-conquer: same total work, same merges, but bottom-up trades the implicit call stack for explicit iteration and wins O(log n) → O(1) space. This 'remove the recursion to save stack space' move recurs in tree traversals (Morris traversal) and DP (rolling arrays).
ComplexityO(n log n) time, O(1) space — There are log n doubling passes; each pass walks and merges all n nodes in O(n) → O(n log n) time. Everything is done with a fixed set of pointers and an explicit split/merge — no recursion, no arrays — so space is O(1).
E · Edge cases and pitfalls7head = [1] — Guard returns immediately; n-counting and passes never run.Explore edge casesHide edge cases
Edge cases handled
head = [1]Guard returns immediately; n-counting and passes never run.head = [2,1]n=2, one pass with size=1 merges [2]&[1] → [1,2].odd length e.g. [5,3,1]Last run is shorter than size; split returns null for the missing run and merge handles a null second list.
Pitfalls
- Forgetting to walk tail to its real end after merge — the next block gets attached in the wrong place.
- Off-by-one in split (using i < size vs i <= size) — cuts runs of the wrong length.
- Not anchoring everything to a dummy node — the head can change every pass.
- Reaching for this version first under time pressure — write top-down, then upgrade.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // Split: find middle with fast/slow, cut before slow. ListNode prev = null, slow = head, fast = head;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Not cutting the list at the midpoint
Finding `slow` as the middle isn't enough. If you don't set `prev.next = null`, the 'first half' still links into the second half, so sortList(head) walks the entire list every time, the input never shrinks, and you get infinite recursion / stack overflow.
Explore the code comparisonHide the code comparison
Not cutting the list at the midpoint
Finding `slow` as the middle isn't enough. If you don't set `prev.next = null`, the 'first half' still links into the second half, so sortList(head) walks the entire list every time, the input never shrinks, and you get infinite recursion / stack overflow.
Don't write this
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode left = sortList(head); // head still reaches slow and beyond!
ListNode right = sortList(slow);Write this instead
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null; // sever — now the halves are disjoint
ListNode left = sortList(head);
ListNode right = sortList(slow);2Returning the dummy sentinel instead of dummy.next
The dummy node has value 0 (or whatever you initialized) and is only a scaffold to avoid first-node special cases. Returning it prepends a bogus node to your sorted list.
Explore the code comparisonHide the code comparison
Returning the dummy sentinel instead of dummy.next
The dummy node has value 0 (or whatever you initialized) and is only a scaffold to avoid first-node special cases. Returning it prepends a bogus node to your sorted list.
Don't write this
dummy = ListNode(0)
tail = dummy
# ... merge loop ...
return dummy # includes the fake 0 nodeWrite this instead
dummy = ListNode(0)
tail = dummy
# ... merge loop ...
return dummy.next # the real head of the merged list3Calling the dump-to-array version O(1) space
The follow-up demands O(1) memory. An auxiliary list/array holding all n values is O(n) space — be precise about this when you present the baseline, and switch to merge sort for the real answer.
Explore the code comparisonHide the code comparison
Calling the dump-to-array version O(1) space
The follow-up demands O(1) memory. An auxiliary list/array holding all n values is O(n) space — be precise about this when you present the baseline, and switch to merge sort for the real answer.
Don't write this
vals = [c.val for c in iterate(head)] # O(n) extra space
vals.sort()
# ... write back ... -> NOT O(1) memoryWrite this instead
# Pointer-based merge sort rewires existing nodes:
# top-down = O(log n) stack, bottom-up = O(1) space.Revise
Carry the pattern into the interview
Pattern to remember
Merge sort on a linked list — split by fast/slow, sort halves, merge
Code pattern to memorize
sort(head):
if head is None or head.next is None: return head
mid = split(head) # fast/slow, CUT before mid
left = sort(head)
right = sort(mid)
return merge(left, right) # dummy + tail spliceRules to remember
- 1Use merge sort, not quicksort — linked lists give sequential access and O(1) merges, but no cheap random pivot access.
- 2Find the middle with fast/slow pointers, then sever the link before the second half (
prev.next = null) or the recursion never terminates. - 3Base case is
head == null || head.next == null— a list of 0 or 1 nodes is already sorted. - 4Merge with a dummy head + tail pointer so the first splice needs no special case; return
dummy.next. - 5The recursive top-down version is O(log n) stack space. Mention bottom-up merge sort for the true O(1)-space answer interviewers love.
Use this pattern when
- Sort a singly linked list with a guaranteed O(n log n) bound
- You need a stable sort and only sequential access is available
- Any divide-and-conquer on a list: split, recurse, combine
- External / streaming sort where random access is expensive
Choose another pattern when
- Data is in an array with random access → just call the library sort (O(n log n), simpler)
- You can tolerate O(n) extra space → dump values into an array, sort, rebuild (easier but not in-place)
- Quicksort instinct → on a linked list the pivot partition is awkward and worst case is O(n²)
- List is tiny / nearly sorted and n is small → insertion sort may be simpler though O(n²)
Interview takeaway
Merge sort is THE sort for linked lists: it only walks forward, merges in O(1) space, and is stable. Master split-via-fast/slow and dummy-node merge here and you've built the two reusable primitives behind Merge Two Sorted Lists, Merge k Sorted Lists, and the merge step of any divide-and-conquer.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternDivide-and-conquer merge sort on a linked list. Recognize it whenever you must sort a list in O(n log n) with only sequential access — merge sort is the answer because its merge step is O(1) space and it never needs random access. It composes the fast/slow split (Middle of the Linked List) with the dummy-node merge (Merge Two Sorted Lists), the same merge that scales up to Merge k Sorted Lists.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Merge Two Sorted ListsThe merge sub-routine used here — dummy node + tail splice. Master it standalone first.
- Merge k Sorted ListsGeneralize merge: pairwise merge in a divide-and-conquer tree, or use a min-heap. O(N log k).
- Middle of the Linked ListThe fast/slow split primitive that finds the midpoint here, isolated.
- Insertion Sort ListComing soonThe O(n²) alternative — sort by inserting each node into a growing sorted prefix.