Sort List
Problem
Given the head of a linked list, return the list after sorting it in ascending order.
Top-down merge sort: find the midpoint with slow/fast pointers and cut the list in two; recursively sort each half; merge the two sorted halves with a standard two-pointer linked-list merge. Recursion depth is O(log n).
4 → 2 → 1 → 31 → 2 → 3 → 4def sort_list(head):
if not head or not head.next: return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next; fast = fast.next.next
mid = slow.next; slow.next = None
L = sort_list(head); R = sort_list(mid)
dummy = ListNode(); tail = dummy
while L and R:
if L.val <= R.val: tail.next = L; L = L.next
else: tail.next = R; R = R.next
tail = tail.next
tail.next = L or R
return dummy.nextfunction sortList(head) {
if (!head || !head.next) return head;
let slow = head, fast = head.next;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
const mid = slow.next; slow.next = null;
const L = sortList(head), R = sortList(mid);
const dummy = { val: 0, next: null }; let tail = dummy;
let l = L, r = R;
while (l && r) {
if (l.val <= r.val) { tail.next = l; l = l.next; }
else { tail.next = r; r = r.next; }
tail = tail.next;
}
tail.next = l || r;
return dummy.next;
}public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode mid = slow.next; slow.next = null;
ListNode L = sortList(head), R = sortList(mid);
ListNode dummy = new ListNode(), tail = dummy;
while (L != null && R != null) {
if (L.val <= R.val) { tail.next = L; L = L.next; }
else { tail.next = R; R = R.next; }
tail = tail.next;
}
tail.next = (L != null) ? L : R;
return dummy.next;
}ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
ListNode* mid = slow->next; slow->next = nullptr;
ListNode *L = sortList(head), *R = sortList(mid);
ListNode dummy(0); ListNode* tail = &dummy;
while (L && R) {
if (L->val <= R->val) { tail->next = L; L = L->next; }
else { tail->next = R; R = R->next; }
tail = tail->next;
}
tail->next = L ? L : R;
return dummy.next;
}Explanation
This sorts a linked list using merge sort, which fits linked lists perfectly because it only ever rewires next pointers and never needs random access by index.
The idea has two halves. First we split the list into two roughly equal pieces. To find the middle without counting, we use the classic slow/fast pointer trick: fast moves two steps for every one step of slow, so when fast reaches the end, slow sits at the midpoint. We cut there with slow.next = None.
Then we recursively sort each half. A list of length 0 or 1 is already sorted, which stops the recursion. Once both halves come back sorted, we merge them by repeatedly attaching whichever of L or R has the smaller head value, walking a tail pointer forward as we link nodes.
A dummy node makes merging clean: we build the result behind it and return dummy.next at the end. When one side runs out, tail.next = L or R appends whatever remains.
Example: 4→2→1→3 splits into [4,2] and [1,3]. Sorting each gives [2,4] and [1,3]. Merging compares heads 2 vs 1, takes 1, then 2, then 3, then 4, producing 1→2→3→4.