[数据结构与算法]LeetCode 23.合并K个升序链表的三种解法

题目概述

题目链接:点我做题

思路

??本题的前置知识是合并两个有序链表，基于这个方法，这里提供三种解法。

一、原地合并法

??既然已经有了合并两个有序链表的方法，我们可以创建一个待返回的链表头结点指针ret，初始值置成$nullptr$，然后遍历一遍链表头结点数组，把ret和当前数组位置的链表头结点$lists[i]$进行一个合并两个有序链表，并且让ret自己接收合并后的链表，遍历完一遍数组，ret的结果就是待返回的结果。
时间复杂度分析：
??假设数组中最长的链表长度为$n$,设数组中有k个链表，第一次合并时，ret链表的长度是0，第一个链表的长度不超过n,所以合并的时间复杂度是$O(n+0)$;不难发现当第i次遍历时，ret的长度最大为$(i?1)?n$，待合并链表的长度最大为$n$，所以合并的时间复杂度是$O(ni)$，对i等于1到k进行求和，利用等差数列求和公式，不难发现时间复杂度为$O(k^{2}n)$.
??此方法的优点显然是没有创建和链表长度和链表个数有关的空间，所以空间复杂度为$O(1)$.
代码:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* ret = nullptr;
        int size = lists.size();
        for (int i = 0; i < size; i++)
        {
            ret = mergetwoLists(ret, lists[i]);
        }
        return ret;
    }
    ListNode* mergetwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode* dummyhead = new ListNode;
        ListNode* tail = dummyhead;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ListNode* next = l1->next;
                l1->next = tail->next;
                tail->next = l1;
                tail = l1;
                l1 = next;
            }
            else
            {
                ListNode* next = l2->next;
                l2->next = tail->next;
                tail->next = l2;
                tail = l2;
                l2 = next;
            }
        }
        tail->next = l1 ? l1 : l2;
        tail = dummyhead->next;
        delete dummyhead;
        return tail;
    }
};

时间复杂度:$O(k^{2}n)$
空间复杂度:$O(1)$

二、归并合并法(递归)

??它的思想很简单，就是两两合并有序链表，然后合并的结果再两两合并，主要困难点在于利用了递归进行实现，我们这里重点讲解代码：
代码:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        //这个函数同时完成递归过程和调用合并有序链表的过程。
        return _merge(lists, 0, lists.size() - 1);
    }
    ListNode* _merge(vector<ListNode*>& lists, 
    int left, int right)
    {
        //控制边界条件
        if (left == right)
        {
            return lists[left];
        }
        //有left大于right的 说明分割区间不存在了 直接返回nullptr
        if (left > right)
        {
            return nullptr;
        }
        //先分割得到终点
        int mid = (left + right) >> 1;
        //同时进行分割过程 并且分割到区间长度为1或区间不存在时
        //会利用上面的返回
        //上面的返回值会被带回 然后进入合并两个有序链表函数
        //合并的结果又会被带回 回到上一层递归
        return MergetwoList(_merge(lists, left, mid),
         _merge(lists, mid + 1, right));
    }
    ListNode* MergetwoList(ListNode* l1, ListNode* l2)
    {
        ListNode* dummyhead = new ListNode;
        ListNode* tail = dummyhead;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ListNode* next = l1->next;
                l1->next = tail->next;
                tail->next = l1;
                tail = l1;
                l1 = next;
            }
            else
            {
                ListNode* next = l2->next;
                l2->next = tail->next;
                tail->next = l2;
                tail = l2;
                l2 = next;
            }
        }
        tail->next = l1 ? l1 : l2;
        tail = dummyhead->next;
        delete dummyhead;
        return tail;
    }
};

时间复杂度分析
??同样设n为链表中最长链表的长度，k为数组中链表个数，显然在分割过程的时间复杂度是常数级的，所以忽略，考虑归并回去的过程，这一过程调用了合并两个有序数组的函数，时间复杂度一定不是常数级的，不难发现每一层归并回去的时间复杂度是$O(kn)$,根据二叉树的知识，总共有$logk$数量级的层数，所以时间复杂度就是$O(nklogk)$.
空间复杂度分析
??因为有递归的栈消耗，层数的数量级是$logk$，所以空间复杂度是$O(logk)$.

三、利用队列进行归并

??这个思路是我对上面的递归归并改非递归的过程想到的，先通过一遍遍历把数组中所有的链表头结点入队列，然后取出队列前两个头结点，归并，将归并结果入队列，然后再取出前两个元素，注意，在取元素的过程中如果取第二个元素时队列为空了，就把第二个元素置成$nullptr$而不是调用$top()$，因为调用这时调用$top()$是越界访问了就，当队列中只剩一个元素时，就说明所有的链表都归并完成了，停止循环，然后返回队列的首元素，这里要控制一下边界条件，如果传进来的lists就是什么都没有的空的，那么q中也是空的，q的大小就是0，就不会进入循环，并且不能使用$front$方法，会导致越界访问，所以我们单独处理一下这种情况，返回$nullptr$即可.

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        queue<ListNode*> q;
        int len = lists.size();
        for (int i = 0; i < len; i++)
        {
            q.push(lists[i]);
        }
        if (q.empty())
        {
            return nullptr;
        }
        while (q.size() != 1)
        {
            ListNode* l1 = q.front();
            q.pop();
            ListNode* l2;
            if (q.empty())
            {
                l2 = nullptr;
            }
            else
            {
                l2 = q.front();
                q.pop();
            }
            q.push(mergetwoLists(l1, l2));
        }
        return q.front();
    }
    ListNode* mergetwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode* dummyhead = new ListNode;
        ListNode* tail = dummyhead;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ListNode* next = l1->next;
                l1->next = tail->next;
                tail->next = l1;
                tail = l1;
                l1 = next;
            }
            else
            {
                ListNode* next = l2->next;
                l2->next = tail->next;
                tail->next = l2;
                tail = l2;
                l2 = next;
            }
        }
        tail->next = l1 ? l1 : l2;
        tail = dummyhead->next;
        delete dummyhead;
        return tail;
    }
};

时间复杂度分析：
??其实这个就是变相的两两归并，所以时间复杂度也是$O(nklogk)$。
空间复杂度分析:
??空间复杂度主要是开辟队列带来的消耗，队列中元素最多的时候就是刚刚把数组中所有元素都弄进来的时候，显然是$O(k)$,这么一想，空间复杂度还不如上一个递归归并呢= =.