描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围:节点总数 0≤𝑛≤50000≤n≤5000,每个节点的val满足 ∣𝑣𝑎𝑙∣<=1000∣val∣<=1000
要求:时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)
示例1
输入:
[{1,2,3},{4,5,6,7}]
返回值:
{1,2,3,4,5,6,7}
示例2
输入:
[{1,2},{1,4,5},{6}]
返回值:
{1,1,2,4,5,6}
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <climits>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param lists ListNode类vector
* @return ListNode类
*/
ListNode* mergeKLists(vector<ListNode*>& lists) {
// write code here
//判断空链表,保证后面的链表都是非空的
for(auto it =lists.begin(); it!=lists.end();){
if(*it==nullptr){
lists.erase(it);
}else {
++it;
}
}
//判断lists是不是空的
if(lists.size()==0){
return nullptr;
}
//定义最小值的索引是-1
//定义最小值为一个很大的值
int minIdx =-1;
int minVal = INT_MAX;
//遍历整个链表,将最小值和最小值的索引找到找到
for(int i=0; i<lists.size();i++){
if(lists[i]->val<minVal){
minVal = lists[i]->val;
minIdx = i;
}
}
//创建一个指针,存放最小值的
ListNode *p = lists[minIdx];
lists[minIdx] = lists[minIdx]->next;
if(lists[minIdx]==nullptr){
lists.erase(lists.begin()+minIdx);
}
//递归
p->next = mergeKLists(lists);
return p;
}
};