23. 合并 K 个升序链表
4 min
题目
解法：优先队列
思路
使用最小堆实现多路归并。每次从堆中取出当前所有链表头节点中的最小值，保证了输出序列的全局有序性。因为每个链表都是升序的，其头节点是剩余元素中的最小值，堆中维护了所有链表的头节点，因此堆顶元素是所有剩余节点中的最小值。将其取出并加入结果后，再将该节点下一个节点加入堆，保持了这一性质。
- Step 1: 创建最小堆，将所有非空链表的头节点加入堆中
- Step 2: 创建虚拟头节点 dummy 和尾指针 tail
- Step 3: 当堆不为空时，取出堆顶节点（最小值），将其接到 tail 后面，更新 tail
- Step 4: 如果取出的节点还有下一个节点，将下一个节点加入堆中
- Step 5: 返回 dummy->next
复杂度
- 时间复杂度: ，其中 N 是总节点数，K 是链表数量。每个节点经历一次入堆和出堆，堆操作耗时 。
- 空间复杂度: ，堆中最多存储 K 个链表的头节点。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 自定义比较规则：由于是最小堆，我们需要 val 小的优先级高
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 在优先队列中，这里的 > 代表最小堆
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 创建最小堆
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
// 1. 将所有非空链表的头节点放入堆中
for (auto head : lists) {
if (head) pq.push(head);
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 自定义比较规则：由于是最小堆，我们需要 val 小的优先级高
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 在优先队列中，这里的 > 代表最小堆
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 创建最小堆
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
// 1. 将所有非空链表的头节点放入堆中
for (auto head : lists) {
if (head) pq.push(head);
}
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
// 2. 每次取出堆顶（最小的节点），挂到结果后面
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
// 如果该节点后面还有，就继续放入堆
if (node->next) {
pq.push(node->next);
}
}
return dummy->next;
}
};