示例 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 = = l i s t s . l e n g t h k == lists.length k==lists.length
0 < = k < = 1 0 4 0 <= k <= 10^4 0<=k<=104
0 < = l i s t s [ i ] . l e n g t h < = 500 0 <= lists[i].length <= 500 0<=lists[i].length<=500
− 1 0 4 < = l i s t s [ i ] [ j ] < = 1 0 4 -10^4 <= lists[i][j] <= 10^4 −104<=lists[i][j]<=104
l i s t s [ i ] lists[i] lists[i] 按 升序 排列
l i s t s [ i ] . l e n g t h lists[i].length lists[i].length 的总和不超过 1 0 4 10^4 104
解法一:
暴力扫描
时间复杂度: O ( K N ) O(KN) O(KN)
空间复杂度: O ( 1 ) O(1) 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 ( N l o g ( K ) ) O(Nlog(K)) O(Nlog(K))
空间复杂度: O ( K ) O(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;}
};