[力扣_23] 合并k个升序链表
题目入口：点击进入
相关算法：
- 暴力破解(顺序合并)——技术不够,分析不来
- 优先队列(小根堆)——技术不够,分析不来
思路和算法：
这道题有四种解法，我只实现了其中两种，另外两种我会在末尾放上其他大佬的博客链接供大家参考，这道题我觉得最有意思的一点就是涉及到了小根堆排序，让我的知识存储量又多了，从我的测试数据来看，暴力破解的时间是小根堆的十倍还多
顺序合并
之前那道合并两个升序链表的题并可以说是这道题的子题，我们可利用它的思想将给定的链表数组实现两两合并，思路是：每次都与后面的链表合并，直到数组为空，也就合并完成
例如：
lists = [[1,4,5],[1,3,4],[2,6]]
我们拿lists[0]作为基准，第一次拿出lists[1]与其两两合并，合并后为：1,1,3,4,4,5(此时lists[0]变为合并后的序列)
然后再拿lists[2]与其合并，并为：
1,1,2,3,4,4,5,6
此时达到循环结束条件，返回即可图解如下：
我们知道了一般情况应该如何解决后，需要判断其特殊情况：
- 若listsSize(链表数组长度)为空的情况下，应返回NULL
- 若链表数组长度为1的情况下，直接返回lists[0]
- 利用一个循环去跳过前导空的链表
- 当中间遇到为空的链表时，应直接跳过
代码如下所示：
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(!listsSize) return NULL;//特判
if(listsSize==1) return lists[0];//特判
struct ListNode*head,*p,*s,*h,*t;
int k=0;
while(k<listsSize && !lists[k])
k++;//跳过前导空的链表
if(k >= listsSize) return NULL;
head=lists[k];
for(int i=k+1;i<listsSize;i++)
{
if(!lists[i]) continue;//跳过中间为空的情况
p=lists[i];
s=head;
h=t=NULL;
while(p&&s)
{
if(p->val < s->val)
{
if(h==NULL)
{
h=p;
p=p->next;
t=h;
}
else
{
t->next=p;
t=t->next;
p=p->next;
}
}
else
{
if(h==NULL)
{
h=s;
s=s->next;
t=h;
}
else
{
t->next=s;
t=t->next;
s=s->next;
}
}
}
if(!p) t->next=s;
else t->next=p;
head=h;
}
return head;
}小根堆排序
若是对堆排序不太了解，可点击此处看大佬的博客，我还没记录到那儿来，和下载下面这段测试代码，来了解堆排序。
对于其他有第三方库的高级语言来说，有了堆(优先队列)这种数据结构，hrad题秒变easy。其实C也就是麻烦了点罢了
我们把三个链表一股脑的全放到堆里面
1->4->5
1->3->4
2->6然后根据小根堆的性质将其排好序。
通过上述链表构造成的小根堆(堆顶元素都比两根要小)
这是一个小根堆，我们只需要每次输出堆顶的元素，直到整个堆为空即可。
执行过程如下:
代码如下所示：
void InsertHeap(struct ListNode*Heap[10001],struct ListNode *e)
{
Heap[0]->val++;
Heap[Heap[0]->val]=e;
int i=Heap[0]->val;
while(i > 1)//自下而上寻找合适的插入位置
{
int preant=i/2;
if(Heap[i]->val < Heap[preant]->val)
{
struct ListNode*temp=Heap[i];
Heap[i]=Heap[preant];
Heap[preant]=temp;
i=preant;
}
else
break;
}
return;
}
struct ListNode* DeleteHeap(struct ListNode *Heap[10001])
{
if(!Heap[0]) return NULL;
struct ListNode *res=Heap[1];
Heap[1]=Heap[Heap[0]->val];//将尾叶子填入根结点的坑中
Heap[0]->val--;
int i=1;
while(i<=(Heap[0]->val)/2)//自上而下寻找合适的插入位置
{
int left=2*i;
int right=left+1;
if(right>Heap[0]->val) right=left;
int Min=Heap[right]->val<Heap[left]->val?right:left;
if(Heap[i]->val>Heap[Min]->val)
{
struct ListNode *temp=Heap[i];
Heap[i]=Heap[Min];
Heap[Min]=temp;
i=Min;
}
else
break;
}
return res;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(!listsSize) return NULL;
if(listsSize==1) return lists[0];
int k=0;
while(k<listsSize && !lists[k])
k++;
if(k >= listsSize) return NULL;
struct ListNode* Heap[10001];//构造堆，首位存放长度
Heap[0]=(struct ListNode*)malloc(sizeof(struct ListNode));
Heap[0]->val=0;
Heap[0]->next=NULL;
for(int i=k;i<listsSize;i++)
{
struct ListNode*p=lists[i];
if(!p) continue;
while(p)
{
InsertHeap(Heap,p);//将元素依次插入堆中
p=p->next;
}
}
struct ListNode *s,*head=NULL;
head=DeleteHeap(Heap);//首元素弹出
s=head;
int i=Heap[0]->val;
while(i>=1)
{
s->next=DeleteHeap(Heap);//后继元素弹出
s=s->next;
i--;
}
s->next=NULL;
return head;
}