Merge k Sorted Lists

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

Solution:
1. Merge sort complexity O(NKlogK), suppose there are N list and each one is K length. Space complexity is O(1). or O(logK) (http://blog.csdn.net/linhuanmars/article/details/19899259)
2. Straight forward thinking. Get the minimum of the head of N list, then add one more from the used list and get the minimum, then add one more from the used list, to implement this algorithm, use priority queue or min heap,  since sorting in heap is logK, every elments (NK in total) has to be added to the min-heap and sorted, the overall complexity is O(NKlogK). Space complexity is O(K). its the size of the min-heap.
These two methods has the same complexity.

Code:
struct cmp{
        bool operator()(ListNode* lhs, ListNode *rhs){
            if(lhs->val < rhs->val)
                return false;
            else
                return true;
        }
};

ListNode* mergeKLists(vector &lists) {
        int K = lists.size();
        if (K == 0) return NULL;
        if (K == 1) return lists[0];

        ListNode *Head(NULL), *cur(NULL);
        ListNode *node(NULL);
        priority_queue, cmp> h;

        // push K list heads into heap
        for(int i=0; i
          if(lists[i]){
            h.push(lists[i]);
            lists[i] = lists[i]->next;
          }

        while(!h.empty()){
          //pop the min of k nodes
          node = h.top(); h.pop();
          if(node->next)
            h.push(node->next);

          //insert node into new list
          if(cur){
              cur->next = node;
              cur = cur->next;
          }
          else{
              Head = cur = node;
          }
        }

        return Head;

}