Given the head of a singly linked list, sort its nodes into non-decreasing order and return the head of the sorted list — using the merge sort algorithm.
Merge sort is the natural fit for a linked list: unlike an array, a list can't jump to its middle in O(1), but it can be split and rewoven purely by rearranging next pointers. Your job is to sort by relinking nodes, not by shuffling values around, and to do it in O(n log n) time.
The list may be empty. Return the new head after sorting.
next. Copying values into an array and sorting also works but uses O(n) extra space and ignores the list structure the problem is testing.slow stop at the end of the first half, giving a clean split. Starting fast at head can leave a two-node list unsplit, causing infinite recursion.Input: head = [9,5,2,8] Output: [2,5,8,9] The four values rearranged into non-decreasing order.
Input: head = [40,20,10,60,50,30] Output: [10,20,30,40,50,60] Sorting the list yields the values in increasing order.
- 0 <= number of nodes <= 10^5 - 0 <= Node.val <= 10^6
Sorting an array is a solved reflex — but a linked list has no random access, so the usual tricks stall. Merge sort is the one classic sort that loves a linked list: it only ever splits and stitches, and both are pure pointer work. This editorial takes you from "how do I even sort a chain of pointers" to a clean O(n log n) in-place merge sort.
In plain words: return the same nodes, re-chained so their values only ever go up as you follow next. Formally, produce a permutation of the list where node.val <= node.next.val for every node.
Worked example — head = 4 -> 2 -> 1 -> 3
list: 4 -> 2 -> 1 -> 3 split: [4 -> 2] [1 -> 3] sort: [2 -> 4] [1 -> 3] merge: 1 -> 2 -> 3 -> 4 ✓
Asking before coding shows you know a sort's behaviour is defined by its edges — empties, ties, and stability all hide there.
“Can the list be empty or a single node?”
Both are already sorted and must return unchanged — this is exactly the recursion's base case, so it can't be an afterthought.
“Are duplicate values allowed, and must equal elements keep their order?”
Duplicates are fine; using less-than-or-equal when merging keeps the sort stable, which is a nice property to mention.
“How large can the list get?”
Up to 100000 nodes rules out any quadratic idea and points straight at an n log n sort.
Before I start, a few quick clarifications.
First — should an empty list or a single node just come back unchanged? I'll treat those as the base case.
And with up to a hundred thousand nodes, I'll go with merge sort for guaranteed n log n and stable ordering on duplicates.
Nothing to compare, nothing to move. This is the recursion's floor — every split eventually shrinks to these trivial lists, and the merges rebuild upward from there.
Walk slow one step and fast two steps at a time; when fast runs off the end, slow sits at the midpoint. Cut the next link right there and you have two independent half-lists — no counting pass required.
4 -> 2 -> 1 -> 3 slow slow lands here cut: [4 -> 2] [1 -> 3]
With both halves sorted, one walk down them — always attaching the smaller front node — produces the merged list in O(n). No values are copied; only next pointers are rewired, which is why merge sort suits linked lists so well.
| Brute force (collect & sort) | Optimal (merge sort in place) | |
|---|---|---|
| Time | O(n log n) | O(n log n) |
| Extra space | O(n) | O(log n) |
| Touches | values | pointers |
Both hit O(n log n) time, but the brute force copies every value into an array and defeats the purpose of a linked-list sort. The optimal version rearranges the nodes themselves. Full code for each is in the Approaches selector below.
Key takeaway
Merge sort is the linked list's sort of choice: split by slow/fast pointers, recurse on each half, and merge two sorted lists by relinking next. It's O(n log n), stable, and never copies a single value.
mergeSort(head): if head is null or head.next is null: return head mid = split head into two halves via slow/fast left = mergeSort(first half) right= mergeSort(second half) return merge(left, right)