算法题---合并K个已经排序好的链表

方法1

使用优先队列，时间复杂度为，kn * log k

// 合并K个已经排序的链表并将其作为一个已排序的链表返回，分析并描述其复杂度
class Solution{
public:
    struct cmp{
        bool operator() (const ListNode *a, const ListNode *b){
            return a->val < b->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists){
        priority_queue<ListNode *, vector<ListNode *>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        ListNode *head = new ListNode(-1);
        ListNode *pre = head;
        while(!q.empty()){
            pre->next = q.top();
            q.pop();
            pre = pre->next;
            if(pre->next) q.push(pre->next);
        }
        return head->next;
    }
};