题解 | #合并k个已排序的链表#

小萌新一枚~

这道题的思路还是比较简单的，只要我们两个两个进行归并就好了。

初始状态是在lists中找出两个不全为NULL的链表进行归并，然后拿得到的新链表作为第一个参数，遍历lists，依次和新链表做归并就好啦

坑点是我一开始没有考虑lists中会出现多个甚至是连续的NULL链表~

可惜复杂度应该不是O(nlogn)，我想想，进行一次merge操作的时间复杂度为O(n)，然后遍历lists的复杂度又是O(n)，这么算来复杂度为O(n^2)了qaq

我看讨论区还是两两归并的比较多哈哈哈

struct ListNode* merge(struct ListNode* a,struct ListNode* b)
{
    if(a==NULL&&b!=NULL)
    {
        return b;
    }
    if(b==NULL&&a!=NULL)
    {
        return a;
    }
    if(a==NULL&&b==NULL)
    {
        return NULL;
    }
    struct ListNode* output;
    if(a->val<b->val)
    {
        output = a;
        a=a->next;
    }
    else
    {
        output = b;
        b=b->next;
    }
    struct ListNode* output_cp = output;
    while(a!=NULL&&b!=NULL)
    {
        if(a->val<b->val)
        {
            output->next = a;
            a=a->next;
        }
        else
        {
            output->next = b;
            b = b->next;
        }
        output = output->next;
    }
    if(a!=NULL)
    {
        output->next = a;
    }
    if(b!=NULL)
    {
        output->next = b;
    }
    return output_cp;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    if(listsLen==0)
    {
        return NULL;
    }
    if(listsLen==1)
    {
        return lists[0];
    }
    struct ListNode* newhead;
    int initial=0;
    while(1)
    {
        newhead = merge(lists[initial], lists[initial+1]);
        if(newhead==NULL)
        {
            initial++;
            if(initial+1>listsLen)
            {
                return NULL;
            }
        }
        else if(newhead!=NULL)
        {
            break;
        }
    }
    for(int i=initial+2;i<listsLen;i++)
    {
        newhead = merge(newhead, lists[i]);
    }
    return newhead;
}