Merge K sorted linked lists
Problem
Given k sorted linked lists, merge them into one sorted list and return its head.
Example 1
Input: [1→4→5, 1→3→4, 2→6] Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
Also asked as: Merge K sorted Linked list
Test cases
Case 1
Input: [[1,4,5],[1,3,4],[2,6]] Expected: [1,1,2,3,4,4,5,6]
Case 2
Input: [] Expected: []
Case 3
Input: [[]] Expected: []
View solutionHide solution1 approach
1. Divide and conquer (pairwise merge)
Time O(N log k)Space O(log k)
Merge lists in pairs, halving the count each round — like merge sort over the array of lists.
function mergeKLists(lists) { const merge2 = (a, b) => { const d = { next: null }; let t = d; 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 d.next; }; if (!lists.length) return null; while (lists.length > 1) { const merged = []; for (let i = 0; i < lists.length; i += 2) merged.push(merge2(lists[i], lists[i + 1] || null)); lists = merged; } return lists[0];}A min-heap of the k current heads also gives O(N log k).