Merge k Sorted Lists
HardLinked lists
You get an array lists of k linked lists, each sorted from smallest to largest. Merge them all into one sorted list and return its head.
On this page each list is written as an array of its values, from head to tail, so lists is an array of arrays. A list can be empty, [], and so can lists itself; the answer is then an empty list, [].
Examples
Input: lists = [[1, 6, 8], [2, 3, 9], [4, 5]] Output: [1, 2, 3, 4, 5, 6, 8, 9]
Every value from the three lists, in one sorted run.
Input: lists = [[], [7], []] Output: [7]
Empty lists add nothing.
Constraints
0 ≤ k ≤ 10⁴- Each list has 0 to 500 nodes, and all of them together at most 10⁴.
-10⁴ ≤ node.val ≤ 10⁴- Each list is sorted in non-decreasing order.
Stuck?
Hint 1
At every step the next node is the smallest of the k current fronts. A min-heap hands you that one in O(log k).
Hint 2
Without a heap, merge the lists in pairs, then the results in pairs, and so on: each round halves the number of lists, so there are only log k rounds.
The idea
Merging two sorted lists is a solved step, so turn k lists into pairs. Merge the lists in pairs, then the results in pairs, and so on: each round halves the number of lists, so every node is relinked about log k times instead of up to k times.
Time O(N log k) for N nodes in allExtra space O(k) for the lists left in each round
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
mergeTwo is the two-list merge: a spare head node, take the smaller front each time, then link on whatever is left of the other list.
function mergeKLists(lists) { const mergeTwo = (a, b) => { const dummy = new ListNode(); let tail = dummy; while (a && b) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a || b; return dummy.next; }; if (!lists.length) return null; let round = lists; while (round.length > 1) { const next = []; for (let i = 0; i < round.length; i += 2) { next.push(mergeTwo(round[i], round[i + 1] || null)); } round = next; } return round[0];}The trap
Folding every list into one running result is a fine plan, but the loop bound stops one list short, so the last list is never merged in. One list on its own comes out right, which hides it. Any input with two or more lists, where the last one has nodes, loses them.
function mergeKLists(lists) { const mergeTwo = (a, b) => { const dummy = new ListNode(); let tail = dummy; while (a && b) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a || b; return dummy.next; }; let merged = lists[0] || null; for (let i = 1; i < lists.length - 1; i++) merged = mergeTwo(merged, lists[i]); // stops one list short return merged;}