Min-Heap (Priority Queue)
Intuition
The idea is to use a min-heap (priority queue) to always pick the smallest element among the heads of all k lists. We start by pushing the head of every non-empty list into the heap. Then we repeatedly extract the minimum node, append it to our result list, and push that node's next pointer into the heap if it is not null. This ensures we always process nodes in sorted order. The heap size is at most k, making each insert and extract operation O(log k).
Algorithm
- Create a min-heap and push the head node of each non-empty list.
- Create a dummy node to build the result list. Initialize a `current` pointer to the dummy.
- While the heap is not empty, extract the node with the smallest value.
- Attach the extracted node to `current.next` and advance `current`.
- If the extracted node has a next node, push it into the heap.
- Return `dummy.next` as the head of the merged list.
Time
O(n log k)SpaceO(k)Code (C++ · Java · Python · Go)
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto* list : lists) {
if (list != nullptr) {
pq.push(list);
}
}
ListNode dummy(0);
ListNode* current = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
current->next = node;
current = current->next;
if (node->next != nullptr) {
pq.push(node->next);
}
}
return dummy.next;
}
};class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
current.next = node;
current = current.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
}import heapq
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
current = dummy
while heap:
val, idx, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.nextimport "container/heap"
type MinHeap []*ListNode
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
node := old[n-1]
*h = old[:n-1]
return node
}
func mergeKLists(lists []*ListNode) *ListNode {
h := &MinHeap{}
heap.Init(h)
for _, list := range lists {
if list != nil {
heap.Push(h, list)
}
}
dummy := &ListNode{}
current := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode)
current.Next = node
current = current.Next
if node.Next != nil {
heap.Push(h, node.Next)
}
}
return dummy.Next
}