#include <queue>
#include <vector>
#include <list>
#include <iostream>

using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x = 0) : val(x), next(NULL) {}
};

class NodeCompare
{
public:
    bool operator()(ListNode *x, ListNode *y) {
        return (x->val > y->val);
    }
};

ListNode *MergeKLists(vector<ListNode *> &lists) 
{
    ListNode * head = NULL;
    ListNode ** previous = &head;
    ListNode *top = NULL;
    // the priority queue works like heap, we could get min value in O(1)
    // delete node and add new node take O(log n), n is size of lists.
    // It's better than compare each head node in lists, which takes O(n) 
    // to find current min
    priority_queue<ListNode *, vector<ListNode *>, NodeCompare> nexts;
    
    for (int i = 0; i < lists.size(); ++i)
        if(lists[i]) //push NULL pointer to queue
            nexts.push(lists[i]);
    
    while(!nexts.empty())
    {
        top = nexts.top();
        nexts.pop();
        (*previous) = top;
        previous = &(top->next);
        if (top->next)
        {
            nexts.push(top->next);
        }
    }
    
    return head;
}


int main(int argc, char** argv)
{
    ListNode lNodes[20];
    vector<ListNode *>  nodes;
    
    for (int i = 0; i < 20; ++i)
    {
        lNodes[i].val = i+1;
        nodes.push_back(lNodes+i);
    }
    
    
    MergeKLists(nodes);
    return 0;
}