学步园

题目：

Merge k sorted
linked lists and return it as one sorted list. Analyze and describe its complexity.

解题：

维持一个小顶堆，每次弹出最小的元素，弹出之后把该元素在原数组中的下一个元素压栈（如果不为空）。

代码：

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<Node> q;
        ListNode *head = new ListNode(-1);
        ListNode *pre = head;
        for(int i = 0; i < lists.size(); i ++) {
            if(lists[i] != NULL) {
                Node now;
                now.x = lists[i];
                q.push(now);
            }
        }
        while(!q.empty()) {
            Node top = q.top();
            q.pop();
            pre->next = top.x;
            if(top.x->next) {
                Node now;
                now.x = top.x->next;
                q.push(now);
            }
            pre = top.x;
        }
        return head->next;
    }
private:
    struct Node {
        ListNode *x;
        bool operator<(const Node p) const{
            return x->val > p.x->val;
        }
    };
};