给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：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
> 思路一：堆排序
class Solution {
public:
// 自定义比较器
struct Comparator {
bool operator()(ListNode *a,ListNode *b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 创建一个小根堆，并定义好排序函数
priority_queue<ListNode*, vector<ListNode*>, Comparator> queue;
std::for_each(lists.begin(), lists.end(), [&queue](ListNode* node){
// 这里跟上一版不一样，不再是一股脑全部放到堆中
// 而是只把k个链表的第一个节点放入到堆中
if (node) queue.push(node);
});
ListNode dummy(-1);
ListNode* p = &dummy;
// 之后不断从堆中取出节点，如果这个节点还有下一个节点，
// 而是只把k个链表的第一个节点放入到堆中
while (!queue.empty()) {
ListNode *tmp = queue.top();
queue.pop();
p->next = tmp;
p = p->next;
if (tmp->next) {
queue.push(tmp->next);
}
}
return dummy.next;
}
};
> 思路二：分治
class Solution {
public:
// 合并两个有序链表
ListNode* merge(ListNode* p1, ListNode* p2){
if(!p1) return p2;
if(!p2) return p1;
if(p1->val <= p2->val){
p1->next = merge(p1->next, p2);
return p1;
}else{
p2->next = merge(p1, p2->next);
return p2;
}
}
ListNode* merge(vector<ListNode*>& lists, int start, int end){
if(start == end) return lists[start];
int mid = (start + end) / 2;
ListNode* l1 = merge(lists, start, mid);
ListNode* l2 = merge(lists, mid+1, end);
return merge(l1, l2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return nullptr;
return merge(lists, 0, lists.size()-1);
}
};
> 思路三：两两合并
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* res = new ListNode();
ListNode* r = res;
while(list1 && list2){
if(list1 -> val > list2 -> val){
//list2 加入res节点
r -> next = list2;
list2 = list2 -> next;
}
else{
r -> next = list1;
list1 = list1 -> next;
}
r = r -> next;
}
r -> next = (list1 == nullptr)?list2:list1;
return res->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if(len == 0) return nullptr;
if(len == 1) return lists[0];
//合并0 和 1的链表 插入最后
ListNode* newlist = mergeTwoLists(lists[0],lists[1]);
lists.push_back(newlist);
//删除0 和 1的链表
lists.erase(lists.begin(),lists.begin()+2);
return mergeKLists(lists);
}
};