LeetCode23. 合并 K 个升序链表（2024秋季每日一题 36）

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

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

示例 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 = [[]]
输出：[]

提示：

$k==lists.length$
$0<=k<=10^4$
$0<=lists[i].length<=500$
$-10^4<=lists[i][j]<=10^4$
$lists[i]$ 按 升序 排列
$lists[i].length$ 的总和不超过 $10^4$

---

解法一：
暴力扫描

• 每次都扫描每个链表头部
• 找到最小的节点，加入到新链表中
• 重复上述过程，直到所有节点都已加入新链表

时间复杂度：$O(KN)$
空间复杂度：$O(1)$

/*** 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* mergeKLists(vector<ListNode*>& lists) {ListNode* h = nullptr, * cur = nullptr;int n = lists.size();while(true){int head = -1;for(int i = 0; i < n; i++){if(lists[i] != nullptr){if(head == -1) head = i;else if(lists[head] -> val > lists[i] -> val){head = i;}}}if(head == -1) break;if(h == nullptr){h = lists[head];cur = h;}else{cur -> next = lists[head];cur = cur -> next;}lists[head] = lists[head] -> next;}return h;}
};

解法二：优先队列优化

时间复杂度：$O(Nlog(K))$
空间复杂度：$O(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* mergeKLists(vector<ListNode*>& lists) {ListNode* h = nullptr, * cur = nullptr;priority_queue<pair<int, ListNode*>, vector<pair<int, ListNode*>>, greater<pair<int, ListNode*>>> q;for(auto p: lists){if(p != nullptr)q.push({p->val, p});}while(!q.empty()){auto t = q.top();q.pop();if(h == nullptr){h = t.second;cur = h;}else{cur -> next = t.second;cur = cur -> next;}ListNode* ne = t.second -> next;if(ne != nullptr) q.push({ne -> val, ne});}return h;}
};