合并K个升序链表的高效算法解析
1. 题目链接
LeetCode 23. 合并K个升序链表
2. 题目描述
给定一个包含k个升序链表的数组lists，要求将所有链表合并为一个新的升序链表并返回。例如，输入三个链表1->4->5、1->3->4和2->6，合并后的结果为1->1->2->3->4->4->5->6。
3. 示例分析
假设输入的三个链表为：
- 链表1:
1 → 4 → 5 - 链表2:
1 → 3 → 4 - 链表3:
2 → 6
合并过程：
- 初始时，堆中依次插入各链表的头节点
1、1、2。 - 弹出最小值
1（链表1），将后续的4加入堆。此时堆顶为1（链表2）。 - 弹出
1（链表2），将后续的3加入堆。堆顶变为2。 - 重复此过程，直到所有节点按升序连接。
4. 算法思路
优先队列（小顶堆）
核心思想：利用优先队列动态维护当前所有链表的最小节点，每次选取最小值插入结果链表，时间复杂度为O(N logk)，N为总节点数，k为链表数量。
步骤：
- 初始化小顶堆：将所有链表的非空头节点入堆。
- 构建结果链表：使用哑节点简化头节点处理。
- 循环合并：
- 弹出堆顶最小节点，链接到结果链表尾部。
- 若该节点有后续节点，将其加入堆。
- 返回结果：释放哑节点，返回合并后的链表头。
5. 边界条件与注意事项
- 空输入处理：当
lists为空或所有链表为空时，直接返回nullptr。 - 链表中途为空：仅将非空节点入堆，避免无效操作。
- 内存管理：正确释放哑节点，防止内存泄漏。
- 比较器设计：C++中优先队列默认为大顶堆，需自定义小顶堆逻辑。
6. 代码实现
class Solution {
public:// 自定义小顶堆比较器struct cmp {bool operator()(const ListNode* l1, const ListNode* l2) {return l1->val > l2->val; // 小顶堆条件}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> heap;// 所有非空头节点入堆for (auto head : lists) {if (head) heap.push(head);}// 哑节点简化处理ListNode* dummy = new ListNode(0);ListNode* tail = dummy;while (!heap.empty()) {ListNode* minNode = heap.top();heap.pop();// 链接到结果链表tail->next = minNode;tail = tail->next;// 后续节点入堆if (minNode->next) {heap.push(minNode->next);}}ListNode* res = dummy->next;delete dummy; // 释放哑节点return res;}
};
代码解析：
- 比较器
cmp：通过重载operator()定义节点比较规则，构建小顶堆。 - 入堆条件：仅非空节点参与合并，避免无效操作。
- 动态维护堆：每次弹出最小节点后，将其后续节点加入堆，保证堆中始终为当前最小候选。
- 哑节点技巧：简化头节点处理逻辑，最后通过
dummy->next返回结果，避免空链表判断。
通过上述方法，可高效合并K个有序链表，适用于大规模数据处理场景。
