DSA problem
Merge k Sorted Lists
You are given an array of k linked lists, lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
The naive idea is to collect every node's value into an array, sort it, and rebuild a linked list — but that costs O(N log N) time and ignores the fact that each input list is already sorted. We can do significantly better by merging in a way that respects the existing order.
A second approach merges the lists pairwise: merge list 0 with list 1, then merge that with list 2, and so on. This works, but each merge re-traverses the growing prefix, giving O(k * N) time in the worst case where N is the total node count.
The optimal idea uses a min-heap of size k to perform a true k-way merge. Push every list's head node into the heap, keyed by its value. Repeatedly pop the smallest node, append it to the output, and if the popped node has a successor push that successor into the heap. Because the heap holds at most k entries and we touch every one of N nodes exactly once, the running time is O(N log k) — a strict improvement over both the naive sort and the pairwise merge for any k > 1.
A subtle implementation detail in some languages: when two nodes have equal values, the heap's comparison falls through to the next tuple field. Including the list index (or a monotonic counter) in the heap entry breaks ties deterministically and avoids the runtime error you would otherwise get from comparing ListNode objects directly.
Examples
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]lists = [][]lists = [[]][]Constraints
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.