LeetCode 23. 合并K个升序链表(C++)

题目地址：力扣

题目难度：Hard

涉及知识点：链表头插法、归并、优先队列（堆）

分析：

解法1：两两合并

思路：一种简单的思路就是每次进行两两合并，比如以第一个链表最为最终链表，那么把剩下的链表都合并到第一个链表上来。由于第一个链表可能为空，因此需要设计一个哨兵节点用来处理这种情况。还需要判断一下数组中没有链表和只有一个链表的情况。

这种方法的缺点就是要扫描第一个链表很多遍，会产生重复的对比，因此时间复杂度比较高，但是不需要额外的空间，因此空间复杂度较低。

class Solution {
public:
    // 两个链表的合并函数
    void merge(ListNode* list1, ListNode* list2)
    {
        // 我们插入节点，因此需要判断的是list1的next节点，而初始化的list1就是哨兵节点
        while (list1->next != nullptr && list2 != nullptr)
        {
            // 只要list2指向节点的值小于等于list1的next节点的值，就将其插入到list1与list1的next节点的中间
            if (list2->val <= list1->next->val) {
                ListNode* tmp = list2;
                list2 = list2->next; 
                tmp->next = list1->next;
                list1->next = tmp;
                list1 = list1->next;
            } // 若list2指向节点值大于list1的next节点的值，就向后移动list1节点 
            else 
                list1 = list1->next;
        }
        // 若list1走到了最后一个节点，那么就把list2指向的后面所有节点接在list1的后面
        if (list1->next == nullptr)
            list1->next = list2;
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 存储链表数组的长度以及哨兵节点
        int sz = lists.size();
        ListNode* sentry = new ListNode(-1);
        // 若链表数组长度为0或为1，直接返回相应结果
        if (lists.size() == 0)
            return nullptr;
        if (lists.size() == 1)
            return lists[0];
        // 数组长度大于1，则将数组中第一个链表作为最后返回的链表，并把它接在哨兵节点后
        sentry->next = lists[0]; 
        // 从第二个链表开始，依次合并每一个链表
        for (int i = 1; i < sz; ++i)
        {
            merge(sentry, lists[i]);
        }
        // 返回哨兵节点的next，即合并后的链表
        return sentry->next;
    }
};

解法2：递归合并（归并）

思路：我们可以采用归并的算法使得链表两两合并，这样能够使得合并步骤的时间复杂度由k降为logk级别，因此下面采用归并的方法合并。

class Solution {
public:
    ListNode* merge(vector<ListNode*> & lists, int start, int end)
    {
        // 若end和start相等，说明只有一个链表，那么返回这个链表即可
        if (end == start) {
            return lists[start];
        }   // 若不等则分为下面的情况 
        else {
            // 定义链1和链2，定义resHead作为哨兵节点，prev用于实现尾插法
            ListNode* list1;
            ListNode* list2;
            ListNode* resHead = new ListNode(0);
            ListNode* prev = resHead;
            // 若只有数组中只有两个元素，那么就把链1和链2设置为这两个链表
            if (end - start == 1) {
                list1 = lists[start];
                list2 = lists[end];
            }   // 否则将数组分为两半，递归求左边的合并结果和右边的合并结果 
            else {
                int mid = (start+end)/2;
                list1 = merge(lists, start, mid);
                list2 = merge(lists, mid+1, end);
            }
            // 将list1和list2进行合并
            while (list1 != nullptr && list2 != nullptr)
            {
                ListNode* tmp;
                if (list1->val <= list2->val) {
                    tmp = list1;
                    list1 = list1->next;
                    tmp->next = prev->next;
                    prev->next = tmp;
                    prev = prev->next;
                } else {
                    tmp = list2;
                    list2 = list2->next;
                    tmp->next = prev->next;
                    prev->next = tmp;
                    prev = prev->next;
                }
            }
            // 若某条链已空，则把prev的next接上另一条链即可
            if (list1 == nullptr)
                prev->next = list2;
            if (list2 == nullptr)
                prev->next = list1;
            // 返回哨兵节点的next
            return resHead->next;
        }
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int sz = lists.size();
        // 若数组中没有链表，那么返回空
        if (sz == 0)
            return nullptr;
        // 对数组进行归并，返回最终结果
        ListNode *res = merge(lists, 0, sz-1);
        return res;
    }
};

解法3：优先队列

思路：既然我们需要合并链表，那我们也可以同时比较。对于数组中每个链表我们在头部都放置一个指针，将最小的元素放进结果链表中。那么只要所有链表都遍历到尾了，我们就得到了结果。那么为了快速找出最小的元素，我们可以借助堆或者优先队列（本质上就是堆）来实现，这里采用STL中的优先队列。

class Solution {
public:
    // 比较函数，用于比较ListNode*类型大小，要定义为static否则下面无法调用
    // 因为这个成员函数并不需要this指针，所以要设置为静态成员函数
    static bool compare(const ListNode* lhs, const ListNode* rhs)
    {
        return lhs->val > rhs->val;
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 先定义数组大小sz以及哨兵节点res，prev节点保存插入点的前驱节点
        int sz = lists.size();
        ListNode* res = new ListNode(0);
        ListNode* prev = res;
        // 优先队列，其中模板的第三个参数可以也写为 decltype(compare)*
        priority_queue<ListNode*, vector<ListNode*>, 
                       bool (*)(const ListNode*, const ListNode*)> pq(compare);
        // 首先把所有链表的头节点加入优先队列中（只要非空）
        for(int i = 0; i < sz; ++i)
        {
            if (lists[i] != nullptr)
                pq.push(lists[i]);
        }
        // 若队列非空，则将最小的节点接在prev的后面，将队头元素出队
        // 接着将最小节点的next入队（只要非空）
        while (!pq.empty())
        {
            prev->next = pq.top();
            pq.pop();
            prev = prev->next;
            if (prev->next != nullptr)
                pq.push(prev->next);
        }
        // 返回哨兵节点的next即最终链表
        return res->next;
    }
};

Accepted

• 133/133 cases passed (28 ms)
• Your runtime beats 36.64 % of cpp submissions
• Your memory usage beats 52.13 % of cpp submissions (13 MB)