当前位置：首页 > ai >正文

【Hot 100】23. 合并 K 个升序链表

ai 2025/5/2 6:37:49

引言

合并 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:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy = new ListNode(0);ListNode* tail = dummy;while(true){if (list1 == nullptr || list2 == nullptr) break;if (list1->val < list2->val){tail->next = list1;list1 = list1->next;}else{tail->next = list2;list2 = list2->next;}tail = tail->next;  // 移动末尾指针}// 连接剩余的节点tail->next = list1 ? list1 : list2;return dummy->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size() == 0) return nullptr;if (lists.size() == 1) return lists[0];// 分治思想，每次合并两个链表，然后直到合并完毕for(int i = 0; i < lists.size() - 1; ++i){lists[i + 1] = mergeTwoLists(lists[i], lists[i + 1]);}return lists[lists.size() - 1];}
};

代码优化

你的解法是顺序合并两个链表的方法，虽然正确但效率可以优化。我来分析并提供几种优化方案：

当前解法分析

时间复杂度：
- 假设k个链表，每个链表平均长度n
- 顺序合并的时间复杂度是O(k²n)（第一次合并n+n，第二次2n+n，…，第k次(k-1)n+n）
优点：
- 实现简单直观
- 复用已有的合并两个链表的方法
缺点：
- 重复遍历节点（前面的链表被多次合并）
- 时间复杂度较高

优化方案

方法一：分治合并（推荐）

将k个链表两两分组合并，再合并结果，时间复杂度O(kn logk)

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2;return dummy.next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) return nullptr;int interval = 1;while (interval < lists.size()) {for (int i = 0; i + interval < lists.size(); i += 2 * interval) {lists[i] = mergeTwoLists(lists[i], lists[i + interval]);}interval *= 2;}return lists[0];}
};

方法二：优先队列（最小堆）

使用优先队列每次取出最小节点，时间复杂度O(kn logk)

class Solution {
public: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;// 初始化优先队列for (auto list : lists) {if (list) pq.push(list);}ListNode dummy(0);ListNode* tail = &dummy;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;}
};

方法三：优化顺序合并

调整合并顺序，减少重复遍历

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 保持你的原有实现}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) return nullptr;// 每次合并相邻的两个链表，然后缩小范围int len = lists.size();while (len > 1) {for (int i = 0; i < len / 2; ++i) {lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);}len = (len + 1) / 2;}return lists[0];}
};

各方法比较

方法	时间复杂度	空间复杂度	实现难度	适用场景
顺序合并	O(k²n)	O(1)	简单	k较小时
分治合并	O(kn logk)	O(logk)	中等	通用最优解
优先队列	O(kn logk)	O(k)	中等	需要流式处理时
优化顺序合并	O(kn logk)	O(1)	中等	避免递归栈空间时