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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <functional>
#include <list>
#include <queue>
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        auto cmp = [](ListNode *a, ListNode *b)  {
            return a->val > b->val;
        };
        priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> pq(cmp);
        for (auto &i: lists) {
            if (i) {
                pq.push(i);
            }
        }
        ListNode *res = nullptr, **ptr = &res;
        while (!pq.empty()) {
            auto now = pq.top();
            pq.pop();
            if (now->next) {
                pq.push(now->next);
            }
            *ptr = now;
            ptr = &((*ptr)->next);
        }
        return res;
    }
};

思路：优先队列。

* 先将所有链表的第一个元素放进去。

* 通过最小堆的性质，获得堆顶节点，也就是最小的节点。

* 该节点的next节点如果不为空，则将其放进堆中。