Merge k Sorted Lists (Min-Heap)
用小根堆合并 k 个有序链表：每次弹出最小节点并推进。
#resource / algorithm
#type / howto
#status / evergreen
#ds / heap
#ds / linked-list
#source / leetcode
[!info] related notes 算法面试题型 MOC 堆常见题
Merge k Sorted Lists (Min-Heap)
LeetCode: https://leetcode.cn/problems/merge-k-sorted-lists/
思路
- 用小根堆（优先队列）按节点值排序。
- 先把每条链表的头节点入堆。
- 循环：弹出最小节点接到结果链表尾部；如果它有
next，把next入堆。
复杂度：
- 总节点数
N，链表数k - 时间：
O(N log k) - 空间：
O(k)
Java Template
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) {
if (head != null) heap.add(head);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
tail.next = cur;
tail = cur;
if (cur.next != null) heap.add(cur.next);
}
tail.next = null;
return dummy.next;
}
}