题解 | #合并k个已排序的链表#优先队列

最简单的方法就是遍历一次，俩俩归并，但可以优化。

需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

struct compare{
    bool operator()(ListNode *a, ListNode *b)
    {
        return a->val > b->val;
    }
};

class Solution {
    priority_queue<ListNode *, vector<ListNode *>, compare> que;
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *node=new ListNode(-1);
        ListNode *ans=node;
        int n=lists.size();//多少个头节点
        if(n==0)
            return {};
        for(auto p:lists)
            if(p)
                que.push(p);
        while(!que.empty())
        {
            ListNode *ln=que.top();
            que.pop();
            node->next=ln;
            node=node->next;
            if(ln->next)
                que.push(ln->next);
        }
        return ans->next;
    }
};