Leetcode 23.合并K个升序链表 链表归并合并

题目描述

合并K个升序链表:原题链接
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路

直接按照归并排序的思路来归并每一条链表。
要注意一些边界情况：

• $K=0$
• $K!=0$但是$K$个链表中所有链表都是NULL的

这两种情况归并完都是NULL，直接返回NULL

其他情况，我们都用归并的方法归并。

代码

大循环的控制思路是一直归并，直到原来的几条链表上的元素被拿空。
用一个变量count来控制。

class Solution {
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    
        if(lists.size()==0)  //如果本来K==0，那么直接返回空
            return NULL;

        bool flag=false;
        int count=0;
        for(int i=0;i<lists.size();i++)
            if(lists[i]!=NULL)
                flag=true;
            else
                count++; //count这里记录下本身就是空的链表的个数
        if(!flag) return NULL; //如果虽然K!=0，但是所有链表都是空的，也返回NULL
        
        ListNode *cur=new ListNode(),*tmp,*res=cur;
        while(count!=lists.size())
        {
       //在每个链表头找最小的元素，以及该链表的下标
            int Min=1e4+10;
            int t=-1;
            for(int i=0;i<lists.size();i++)
            {
    
                if(!lists[i]) continue; //如果碰到空的链表了，跳过
                ListNode *p=lists[i];
                if(p->val<=Min)
                {
    
                    Min=p->val;
                    t=i;
                }
            }
            //接到结果链表上
            tmp=new ListNode(Min);
            cur->next=tmp;
            cur=tmp;
            //把原来链表上这个元素拿掉
            lists[t]=lists[t]->next;
            if(!lists[t]) count++; //如果拿完，当前链表就为空了，则count记录一下
        }
        res=res->next; //要把一开始的首部0结点给过滤掉
        return res;
    }
};