Sort List
Given the head of a singly linked list , return the list after sorting it in ascending order. Use merge sort : find the middle node with fast and slow pointers , sort each half recursively, then merge the two sorted halves by relinking nodes instead of writing into an array.
Constraints
- The number of nodes in the list is in the range [0, 5 × 104]
- -105 ≤ Node.val ≤ 105
Example
Input
head = [4, 2, 1, 3]Output
[1, 2, 3, 4]Explanation Splitting the list in half at the middle node and merging the sorted halves back together produces [1, 2, 3, 4].
In plain terms
- Linked list
- A chain of items where each item points to the next one, like a scavenger hunt where each clue tells you where to find the next.
Cut at the middle, sort each half, merge by relinking
04
12
21
33
Statussplit
Find the middle node and cut the list into two halves: [4, 2] and [1, 3].
What happens in this step
list: 4 → 2 → 1 → 3 fast/slow pointers: slow advances to the node holding 1, with prev trailing at the node holding 2 — prev.next is cut to null there. left half: 4 → 2 right half: 1 → 3 Each half still has more than one node, so both recurse further before merging.
Step 1 of 5
Steps to visualize
- Use fast and slow pointers to find the middle node, then cut the list into two halves there.
- Recursively sort each half the same way.
- Merge the two sorted halves by relinking nodes — the same two pointer walk used to merge two sorted arrays, just following next pointers instead of array indices.
- The recursion bottoms out at a single node or an empty list, which are already sorted.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
04
12
21
33
Statussplit
Find the middle node and cut the list into two halves: [4, 2] and [1, 3].
What happens in this step
list: 4 → 2 → 1 → 3 fast/slow pointers: slow advances to the node holding 1, with prev trailing at the node holding 2 — prev.next is cut to null there. left half: 4 → 2 right half: 1 → 3 Each half still has more than one node, so both recurse further before merging.
Step 1 of 5
Solution
function sortList(values) {
function buildList(arr) {
const dummy = { val: 0, next: null };
let curr = dummy;
for (const v of arr) {
curr.next = { val: v, next: null };
curr = curr.next;
}
return dummy.next;
}
function toArray(head) {
const result = [];
let node = head;
while (node) {
result.push(node.val);
node = node.next;
}
return result;
}
function getMiddle(head) {
let slow = head;
let fast = head;
let prev = null;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev) prev.next = null; // cut the list into two halves
return slow;
}
function mergeLists(a, b) {
const dummy = { val: 0, next: null };
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;
return dummy.next;
}
function sort(head) {
if (!head || !head.next) return head;
const middle = getMiddle(head);
const left = sort(head);
const right = sort(middle);
return mergeLists(left, right);
}
return toArray(sort(buildList(values)));
}- Time
- O(n log n)
- Space
- O(log n)
Test cases
| Input | Expected | Covers |
|---|---|---|
head = [4, 2, 1, 3] | [1, 2, 3, 4] | example from the docstring |
head = [] | [] | empty list |
head = [5] | [5] | smallest valid input, a single node |
head = [1, 2, 3] | [1, 2, 3] | already sorted list |
head = [3, 2, 1] | [1, 2, 3] | fully descending list |
head = [2, 2, 1] | [1, 2, 2] | repeated values |
head = [-1, -3, 2] | [-3, -1, 2] | mix of negative and non-negative values |
head = [2, 1] | [1, 2] | boundary case, exactly two nodes |