Merge K Sorted Lists

/*

http://leetcode.com/onlinejudge#question_115

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
*/
typedef std::pair<int, ListNode*> heapvalue_t;

bool operator < ( const heapvalue_t & a, const heapvalue_t & b)
{
    return a.first > b.first; // for minheap
}

class Solution {
public:

    ListNode * mergeKLists(vector<ListNode *> &lists)
    {
        if(lists.empty()) { return NULL; }

        std::priority_queue<heapvalue_t> minheap;
        const int N = lists.size();

        for(int i = 0; i < N; ++i)
        {
            ListNode * node = lists[i];
            if(node) { minheap.push(make_pair(node->val, node)); }
        }

        minheap.push(make_pair(INT_MAX, (ListNode*)NULL)); // satellite - end of stream
        ListNode * head = NULL, * tail;

        while(!minheap.empty())
        {
            ListNode * node = minheap.top().second;
            minheap.pop();

            if(!head) { head = tail = node; }
            else if(tail) { tail->next = node; tail = node; }

            if(node && node->next)
            {
                minheap.push(make_pair(node->next->val, node->next));
            }
        }
        return head;
    }
};