[力扣_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
此时达到循环结束条件,返回即可

图解如下:

img

我们知道了一般情况应该如何解决后,需要判断其特殊情况:

  • 若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;
}

小根堆排序

若是对堆排序不太了解,可点击此处看大佬的博客,我还没记录到那儿来,和下载下面这段测试代码,来了解堆排序。

Heap'Push_and_Pop.c

对于其他有第三方库的高级语言来说,有了堆(优先队列)这种数据结构,hrad题秒变easy。其实C也就是麻烦了点罢了

我们把三个链表一股脑的全放到堆里面

  1->4->5
  1->3->4
  2->6

然后根据小根堆的性质将其排好序。

img通过上述链表构造成的小根堆(堆顶元素都比两根要小)

这是一个小根堆,我们只需要每次输出堆顶的元素,直到整个堆为空即可。
执行过程如下:

img

代码如下所示:

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;
}

本文链接:

https://nullcode.fun/69.html
1 + 7 =
快来做第一个评论的人吧~