Given the head of a singly linked list, sort the list in ascending order and return the head of the sorted list.
Your function receives and returns a ListNode chain; the examples below show each list in array notation for readability — [4, 2, 1, 3] is the chain 4 -> 2 -> 1 -> 3, which sorts to 1 -> 2 -> 3 -> 4. An empty input ([], i.e. head is null) is valid and should return an empty list.
Example
Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
Intuition
A first pass ignores the list structure entirely: copy every node's value into a plain array, let a comparison sort put the array in order, then walk the list a second time overwriting each node's value with the sorted array, in order.
function sortList(head) {
// Collect every node's value into a plain array.
const values = [];
for (let node = head; node; node = node.next) {
values.push(node.val);
}
// Numeric sort — the default comparator would sort lexicographically.
values.sort((a, b) => a - b);
// Walk the list again, overwriting each node's value in sorted order.
let node = head;
let i = 0;
while (node) {
node.val = values[i];
i++;
node = node.next;
}
return head; // same nodes, same head — only the values changed
}This is O(n log n) time — the array sort dominates — but it treats the list purely as a bag of values: it needs a whole separate array to hold them, and it never rewires a single next pointer. Can we do better on space?
The key observation: a linked list already supports O(1) splice — unlike an array, no shifting is needed to cut it in two or stitch two pieces back together. That means merge sort can run directly on the list, with no auxiliary buffer: find the midpoint with the fast/slow pointer technique (the same Linked lists fast/slow scan that finds a list's middle node), sever the list there into two standalone sublists, recursively sort each half, then merge the two sorted halves back together node-by-node — the identical splice used to solve Merge Two Sorted Lists.
All of that work is pointer rewiring, not allocation, so the extra space drops from O(n) for the array down to O(log n) for the recursion stack. The stored solution's merge step builds the result with a dummy head and a tail cursor that always attaches the smaller of the two current heads (a/b) and advances it — the walkthrough below uses the exact same names, labeling the dummy d.
Walking it through:
sortList([6, 2, 8, 4]) — find the midpoint with fast/slow
fast starts one node ahead of slow (at head.next) so, on an even-length list, slow ends up on the first of the two middle nodes.
One iteration: fast jumps two nodes to index 3, slow moves one to index 1. fast.next is now null, so the loop stops here — slow marks the midpoint.
Severing index 1's link splits one list into two standalone chains: 6 -> 2 (indices 0–1) and 8 -> 4 (indices 2–3, no longer reachable from the first half).
left half [6, 2] sorts itself to 2 -> 6
6 and 2 are each a single node — already "sorted" on their own. Merging them picks the smaller head first: 2, then 6.
right half [8, 4] sorts itself to 4 -> 8
Same pattern: 8 and 4 are each already "sorted" alone. Merging them puts the smaller head, 4, first.
merging 2 -> 6 with 4 -> 8 (d = dummy head)
Two sorted sublists — a: 2 -> 6, b: 4 -> 8 — ready to merge. The dummy head (d) avoids special-casing the very first node of the result.
2 is the smaller of the two heads, so the dummy's next is wired straight to it. a advances to its next node, 6.
6 loses this round to 4, so node 2's link is rewired to point at 4 instead of its old neighbor, 6. b advances to 8.
6 finally gets spliced in — node 4's link is rewired to point at it. a is now exhausted (null): the left sublist is fully merged in.
Whatever's left of b (just node 8) is spliced on wholesale. Reading from the dummy's next: 2 -> 4 -> 6 -> 8 — the two sublists are fully merged into one sorted chain.
Optimization
Top-down merge sort (fast/slow split + linked-list merge)
Merge sort adapts naturally to a linked list because the "merge" step doesn't need random access — it's the same two-pointer splice used to merge two sorted lists, and unlike an array merge it needs no auxiliary buffer.
The recursive shape:
1. Base case — a list of 0 or 1 nodes is already sorted; return it as-is.
2. Split — find the midpoint with the classic fast/slow pointer technique: slow advances one node per step, fast advances two, so when fast runs off the end slow sits at the midpoint. Crucially, sever the link right after slow (slow.next = null) so the first half becomes its own standalone list instead of still trailing into the second half.
3. Recurse — sort each half independently.
4. Merge — splice the two sorted halves back together one node at a time, always taking the smaller current head, using a dummy head to avoid special-casing the first node.
O(n log n) time (log n levels of splitting, each doing O(n) work to merge). O(log n) extra space for the recursion stack — the merge itself reuses the existing nodes rather than allocating new ones. (The classic follow-up for true O(1) space is an iterative bottom-up merge sort that merges runs of size 1, 2, 4, … without recursion; the top-down recursive version here is simpler to read and is the one implemented.)
function sortList(head) {
// Base case: empty list or a single node is already sorted.
if (!head || !head.next) return head;
// Split into two halves using fast/slow pointers: fast moves two nodes per
// step, slow moves one, so slow lands on the midpoint when fast runs out.
let slow = head;
let fast = head.next; // start fast one ahead so slow ends at the *first* of two middles
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
const secondHalf = slow.next;
slow.next = null; // sever the first half so it's a standalone list
const left = sortList(head);
const right = sortList(secondHalf);
return mergeTwoSorted(left, right);
}
// Classic sorted-linked-list merge, reusing nodes (no new allocation besides the dummy).
function mergeTwoSorted(a, b) {
const dummy = new ListNode(0);
let tail = dummy;
while (a && b) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a || b; // splice on whichever half has leftovers
return dummy.next;
}Complexity analysis
Time complexity: O(n log n). Here's why:
- Finding the midpoint with the fast/slow scan takes O(k) for a list of length k, so splitting a list of length n costs O(n) at that level.
- Halving the length at each level of the recursion means there are O(log n) levels before the sublists bottom out at length 1.
- At each level, the merges together touch every node in the list exactly once, so each level costs O(n) total (not per merge call — summed across all the merges at that level).
So it's O(n) work per level × O(log n) levels — the overall time is O(n log n).
Space complexity: O(log n). Here's why:
- The split step and the merge step both just rewire existing nodes'
nextpointers — no new nodes are allocated (thedummynode created inside each merge call is discarded once that call returns). - The only real extra space is the call stack from recursing into each half; its depth is how many times the list can be halved before reaching length 1, which is O(log n).
The sorted list isn't a separate structure — it's the same nodes, relinked — so it isn't counted as extra space. (The brute force's array of values, by contrast, is O(n) extra space on top of the list itself.)
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| head = []null | []null | Empty list — nothing to split or merge; returns immediately. |
| head = [-7]-7null | [-7]-7null | Single node — the base case, already "sorted" by definition. |
| head = [10,-3]10-3null | [-3,10]-310null | Two nodes out of order — the smallest merge that actually swaps anything. |
| head = [7,7,7]777null | [7,7,7]777null | All-equal values — every merge comparison ties, and ties must still preserve every copy. |
| head = [4,1,4,2,1]41421null | [1,1,2,4,4]11244null | Duplicates scattered across both halves of the initial split, exercising dedup-free merging (equal values are kept, not collapsed). |
Try it yourself
Write your solution against the real judge before checking the reference.