Heap / Priority Queue
LC #23Hard
Merge k Sorted Lists
Heap / Priority Queue
AmazonMetaGoogleMicrosoftBloombergProblem
Merge k sorted linked lists into one sorted linked list.
linked-listheapdivide-and-conquer
Constraints
- ›0 ≤ lists.length ≤ 10⁴
- ›0 ≤ lists[i].length ≤ 500
- ›-10⁴ ≤ lists[i][j] ≤ 10⁴
- ›Total nodes ≤ 10⁴
Example
Input
lists = [[1,4,5],[1,3,4],[2,6]]Output
[1,1,2,3,4,4,5,6]Why
Merge all 3 sorted linked lists using a min-heap to always pick the smallest next node