目录
题目：
示例：
分析：
代码：
题目：
示例：
分析：
题目给我们一个链表数组，数组里的链表都是升序的，让我们合并这些链表，要求合并之后还是升序的。
最简单最直观的做法就是遍历整个数组，把每个链表的节点都取出来塞到一个容器里，然后对容器进行升序排序，接着按顺序重新串连成新的链表就可以。
我本以为这么做有些暴力，不太好，结果：
emmm。。。。
也没什么不好的，最高端的食材往往只需要最简单的烹饪方式，最困难的题目往往只需要最朴素的解法。
那除了这个取出来再排序的“暴力”解法，那还有一种就是不用我们亲自去“暴力”的方法。
那就是利用小顶堆的堆顶永远是堆内的最小元素这一特性，我们把元素全部塞进小顶堆。
接着进入while循环，只要堆不为空，那我就把堆顶取出来接到新链表后。
最后一样也是可以获取到一条升序的链表。
两种解法没什么本质上的区别，不同的就是第一种我们手动去排序了，第二种是人家帮我们去排序了。没啥本质上的区别，运行的结果也是一样的。
既然这种偏“暴力”的解法都还解得不错，那么用这种“暴力”解法就好了。
如果一定要利用到原本链表就升序的这个特性的话，也可以。
我们先进入while循环，循环的条件是整个原数组里的链表至少有一个不为空指针节点。
接着进入一层for循环，去寻找数组里那个链表头的值最小（不唯一），接着把它取出来放到新链表的后面，再把这个链表往后移动。
直到原数组里的链表都变成了空指针节点，那么我们就是合并完成了。
我个人觉得还不如上面的两种“暴力”解法简单。文章来源：https://www.toymoban.com/news/detail-643866.html
不过思路提供给大家了，怎么做都可以，黑猫白猫能抓老鼠的都是好猫。文章来源地址https://www.toymoban.com/news/detail-643866.html
代码：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//把节点塞到一个容器里排序后重新连接成链表
vector<ListNode*>cache;
for(auto list:lists){
while(list){
cache.push_back(list);
list=list->next;
}
}
sort(cache.begin(),cache.end(),[](auto a,auto b){return a->val<b->val;});
ListNode* res=new ListNode(0);
ListNode* cur=res;
for(ListNode* node:cache){
cur->next=node;
cur=cur->next;
}
cur->next=nullptr;
return res->next;
//把节点塞到一个小顶堆里,然后生成链表
auto cmp=[](auto a,auto b){return a->val>b->val;};
priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)>minpq;
for(auto list:lists){
while(list){
minpq.push(list);
list=list->next;
}
}
ListNode* res=new ListNode(0);
ListNode* cur=res;
while(!minpq.empty()){
cur->next=minpq.top();
minpq.pop();
cur=cur->next;
}
cur->next=nullptr;
return res->next;
}
};到了这里，关于【力扣每日一题】2023.8.12 合并K个升序链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
