企业官网建设流程全解析

题目描述：

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2：

输入：lists = []输出：[]

示例 3：

输入：lists = [[]]输出：[]

解题思路：

方法一：辅助数组法

我看到合并几个升序链表时，就想起数据结构里曾学过的归并排序了，因为归并排序就是要求链表得是有序的，但是具体代码实现还不熟，所以为了快速解题，我还是用了自己的思路。

我的思路是：把所有链表的值全部存入一个 vector，排序，再重建一个新链表。

具体步骤：

1. 遍历所有链表：把每个节点的值存入temp

2. 排序：用sort对temp排序

3. 重建：用排序后的值新建链表节点，连接成新链表

4. 返回：返回新链表头节点

用例子走一遍：

lists = [[1,4,5], [1,3,4], [2,6]]

代码实现：

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* ans=nullptr; vector<int> temp; for(int i=0;i<lists.size();i++){ while(lists[i]!=nullptr){ temp.push_back(lists[i]->val); lists[i]=lists[i]->next; } } sort(temp.begin(),temp.end()); ListNode* h=nullptr; ListNode* t=nullptr; for(int x:temp){ ListNode* node=new ListNode(x); if(h==nullptr){ h=node; t=node; } else{ t->next=node; t=node; } } return h; } };

复杂度分析：

假设：

• k= 链表数量

• n= 所有节点的总数

缺点：

1. 空间复杂度 O(n)，不是最优

我的方法需要：

• vector<int> temp存储所有值：O(n)

• 新建 n 个节点：O(n)

总共 O(n) 额外空间，而最优解法可以做到O(k)（k 是链表数量）。

2. 没有利用"每个链表已经有序"这个条件

题目给出的每个链表本身已经是有序的。我把它们全部打散重新排序，浪费了已有的有序信息。

3. 新建了所有节点，没有复用原节点

我用new ListNode(x)新建了 n 个节点，而最优解法直接复用原链表的节点，不需要新建。

4. 修改了原链表指针

while(lists[i] != nullptr){ temp.push_back(lists[i]->val); lists[i] = lists[i]->next; // ❌ 修改了 lists[i]，原链表头指针丢失 }

我把lists[i]移动到了末尾，原链表的头指针丢失了。虽然本题不影响结果，但修改输入参数不是好习惯。

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

核心思路：

用最小堆维护 k 个链表的当前头节点，每次取出最小的节点接到结果链表上。

因为每个链表已经有序，所以每个链表的最小值就是它的头节点。我们只需要在 k 个头节点中找最小的，取出来，然后该链表头节点后移。

具体过程示例：

lists = [[1,4,5], [1,3,4], [2,6]]

初始堆: [1, 1, 2]（三个链表的头节点） 第1步: 取出 1（来自链表1），链表1后移，堆变成 [1, 2, 4] 结果: 1 第2步: 取出 1（来自链表2），链表2后移，堆变成 [2, 3, 4] 结果: 1 -> 1 第3步: 取出 2（来自链表3），链表3后移，堆变成 [3, 4, 6] 结果: 1 -> 1 -> 2 ...以此类推 最终: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 ✅

代码实现：

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { // 自定义比较：小根堆 auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); // 把每个链表的头节点加入堆 for (ListNode* node : lists) { if (node != nullptr) { pq.push(node); } } ListNode* dummy = new ListNode(0); ListNode* curr = dummy; while (!pq.empty()) { // 取出最小节点 ListNode* node = pq.top(); pq.pop(); // 接到结果链表 curr->next = node; curr = curr->next; // 该链表后移，把下一个节点加入堆 if (node->next != nullptr) { pq.push(node->next); } } return dummy->next; } };

复杂度分析:

比我的方法更快：当k << n时，O(n log k)远小于O(n log n)。

方法三：分治归并（两两合并）

思路：把 k 个链表两两合并，像归并排序一样分治。

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) return nullptr; return divide(lists, 0, lists.size() - 1); } private: ListNode* divide(vector<ListNode*>& lists, int left, int right) { if (left == right) return lists[left]; int mid = left + (right - left) / 2; ListNode* l1 = divide(lists, left, mid); ListNode* l2 = divide(lists, mid + 1, right); return merge(l1, l2); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* curr = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; } curr->next = l1 ? l1 : l2; return dummy.next; } };

复杂度：时间 O(n log k)，空间 O(log k)（递归栈）

三种方法对比：