Merge sort for linked lists
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: []
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;}