合并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个有序链表,适用于大规模数据处理场景。