Merge sort for linked lists

Medium

Problem

Sort a linked list in O(n log n) time using merge sort: split at the middle, sort both halves, and merge them.

Example 1

Input:  4 → 2 → 1 → 3
Output: 1 → 2 → 3 → 4

Also asked as: Merge Sort For Linked lists

Test cases

Case 1

Input:    [4,2,1,3]
Expected: [1,2,3,4]

Case 2

Input:    [-1,5,3,4,0]
Expected: [-1,0,3,4,5]

Case 3

Input:    [2,1]
Expected: [1,2]

Case 4

Input:    [1]
Expected: [1]

Case 5

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Split by slow/fast, sort halves, merge

Time O(n log n)Space O(log n) recursion

Find the middle with a fast/slow walk, cut, recursively sort each half, then merge the two sorted lists. Merge sort is preferred for lists (no random access needed, O(1) extra).

function 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 = { next: null };
let t = dummy, a = L, b = R;
while (a && b) {
if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; }
t = t.next;
}
t.next = a || b;
return dummy.next;
}