23 合并K个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/description/
本题在21 合并两个升序链表的基础上进行加难
解法一:顺序合并
每相邻两个合并升序链表
/**
* 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 {
private:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
ListNode* head = new ListNode();
ListNode* tail = head;
while(list1 != nullptr && list2 != nullptr){
if(list1->val < list2->val){
tail->next = list1;
list1 = list1->next;
}
else{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 == nullptr ? list2 : list1;
return head->next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans = nullptr;
for(int i = 0; i < lists.size(); i++){
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};
解法二: 分治合并
类似于快速排序,分组合并
/**
* 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 {
private:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
ListNode* head = new ListNode();
ListNode* tail = head;
while(list1 != nullptr && list2 != nullptr){
if(list1->val < list2->val){
tail->next = list1;
list1 = list1->next;
}
else{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 == nullptr ? list2 : list1;
return head->next;
}
ListNode* merge(vector<ListNode*>& lists,int l, int r){
if(l == r)
return lists[l];
if(l > r)
return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 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:
struct cmp{
bool operator()(const ListNode* p1, const ListNode* p2){
// 小根堆
return p1->val > p2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* dummyNode = new ListNode(-1);
ListNode* p = dummyNode;
priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
for(ListNode* head : lists){
if(head != nullptr)
heap.push(head);
}
while(!heap.empty()){
// 取出值最小的链表头
ListNode* head = heap.top();
heap.pop();
// 去掉尾部,防止产生环
ListNode* nxt = head->next;
head->next = nullptr;
// 插入到新链表中
p->next = head;
p = p->next;
// 更新链表头到heap
if(nxt != nullptr)
heap.push(nxt);
}
return dummyNode->next;
}
};
复杂度分析:
时间复杂度: