题目内容

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

题解

本题求解思路主要是基于二维链表的求解思路，每次遍历全部链表上对应的指针，求出全局最小值，将该节点接入新链表中，然后直到循环结束。因为链表有序，因此采用指针算法没有任何问题。

这里需要注意两个问题

1、有关求全局最小值的操作优化：使用小根堆的数据结构。具体解释如下：

小根堆，是一种父节点的值小于或等于其下方所有子节点的值的数据结构。我们将每个链表的指针节点存储到堆的数据结构中，每次取出顶点元素节点，时间复杂度为O(1)，然后将对应最小指针的next节点添加到堆中，由于我们是小根堆，因此堆需要重新排序，若假设总链表个数为k，则时间复杂度为O(logk)。因此，总体的事件复杂度为O(nlogk)。

2、对C++语言特性的运用即：STL容器以及仿函数的运用。具体解释如下：

在C++中，我们通常会采用STL容器来实现数据结构中的操作，比如vector容器、stack栈模型、queue队列模型、list链表模型、priotriy_queue优先级队列模型等等。在本题中，就是使用priotriy_queue优先队列模型，其具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的，因此我们使用此容器来当成一个堆的数据结构。

同时，由于该容器默认为大根堆，因此需要对其内部的比较规则进行重新修改，这里采用仿函数的机制进行。

仿函数，通俗点来说就是使一个类的使用看上去像一个函数，其实现就是类中实现一个operator()方法，这个类就有了类似函数的行为，就是一个仿函数类。在实现上，可以在C++中的结构体中重载一个operator()方法实现自定义比较，然后将该结构体在堆的定义上，当做参数传入即可，具体实现请看代码。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        /*
            这里需要自定义一个比较函数
        */
        struct Cmp{
            bool operator() (ListNode* a, ListNode* b){
                return a -> val > b -> val;
            }
        };

        /*
            思路与双指针类似。也是在每个链表中添加一个指针，然后循环求出全局最小值，然后重复上述操作得出最终的归并后的有序链表。
            但是，求出全部指针中的最小值，不仅可以用循环的方式做，也可以用堆这种数据结构来做。假设所有链表的总长度为n，链表个数为k
            那么通过循环的方法的时间复杂度是nk，采用堆的数据结构的话的时间复杂度是nlogk
        */
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap; //这里定义的话，如果不传入vector<ListNode*>以及一个比较函数Cmp，堆会按照地址的大小进行排序，显然不是我们所希望的。同时，Cmp这个函数需要定义一个结构体，重载操作符并返回值的大小判断。
        auto dummy = new ListNode(-1), tail = dummy; //定义虚拟头结点，并定义一个新链表的尾结点
        for(auto l : lists) if(l) heap.push(l); //将空链表去掉

        //当堆里面有元素的时候，进行循环
        while(heap.size()){
            auto t = heap.top(); //取出对顶元素，即为全局最小值
            heap.pop(); //将堆顶元素弹出

            tail = tail -> next = t;//将最小值插入并且将尾结点更新
            if(t -> next) heap.push(t -> next);//如果t有下一个节点，那么把下一个节点添加到堆中，相当于把指针向前移动一位。
        }
        return dummy -> next;
    }
};