Sort List

The problem. Given the head of a singly linked list, return it sorted in ascending order. Aim for O(n log n) time.

Example

4 -> 2 -> 1 -> 3        ->  1 -> 2 -> 3 -> 4
-1 -> 5 -> 3 -> 4 -> 0  ->  -1 -> 0 -> 3 -> 4 -> 5
(empty)                 ->  (empty)

The idea: merge sort fits linked lists

Quick sort and heap sort jump around by index, which a linked list can't do. Merge sort only ever walks forwards: finding the middle takes a slow and a fast pointer, splitting is one next = null, and merging two sorted lists just relinks existing nodes — no extra array, no copying. That makes it the standard way to sort a linked list.

1. Copy the values, sort, write them back

1function sortList(head) {2  const values = [];3  for (let node = head; node !== null; node = node.next) values.push(node.val);4  values.sort((a, b) => a - b);5  let i = 0;6  for (let node = head; node !== null; node = node.next) node.val = values[i++];   // write them back in order7  return head;8}

Time O(n log n), space O(n). It works, but it needs an array as big as the list, and it changes the values rather than the links — which interviewers usually rule out.

2. Merge sort on the list

1function sortList(head) {2  if (head === null || head.next === null) return head;   // 0 or 1 nodes: sorted3  let slow = head, fast = head.next;                      // find the middle4  while (fast !== null && fast.next !== null) {5    slow = slow.next;6    fast = fast.next.next;7  }8  const right = slow.next;9  slow.next = null;                                       // cut the list in two10  return mergeLists(sortList(head), sortList(right));11}12 13function mergeLists(a, b) {14  const dummy = new ListNode(0);15  let tail = dummy;16  while (a !== null && b !== null) {17    if (a.val <= b.val) { tail.next = a; a = a.next; }18    else { tail.next = b; b = b.next; }19    tail = tail.next;20  }21  tail.next = a !== null ? a : b;                         // attach whatever is left22  return dummy.next;23}

Time O(n log n), space O(log n) for the recursion. Starting fast at head.next makes slow stop at the end of the left half, so a two-node list splits into one and one instead of looping forever. A bottom-up version — merge runs of 1, then 2, then 4, … — removes the recursion and reaches O(1) extra space.

Comparing the approaches

Edge cases to test

Variations