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

优先队列合并：时间 O(kn * logk), 空间 O(k)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    // 重载 "小括号()" 是因为 STL容器 在比较的时候用的是 结构体的小括号运算符
    struct Cmp {
        bool operator() (ListNode*a, ListNode*b) {
            return a->val > b->val;  // 优先队列本来是大根堆，所以这里需要反过来把大根堆的小于号换成大于号就变成了小根堆了，在堆中大的在下面，小的在最上面也就是小根堆
        }
    };  // 注意 此处 有个 ';', 很容易忘记
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 优先队列 定义：priority_queue<Type, Container, Functional>
        // 因为 优先队列中存的是 链表头结点的地址, 我们要比较的是结点的值 而不是 地址
        // 所以 要自己定义 Cmp 比较 结点的值
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        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;  // 把当前结点插到尾结点后面(tail->next = t)，因为插入之后t会变成新的尾结点，所以再把尾结点更新一下（tail = tail->next = t）
            if (t->next) heap.push(t->next);  // 如果t还有下一个结点，就要把下个节点插进来，相当于把指针往后移动一位

        }

        return dummy->next;  // 返回虚拟头结点next
    }
};