Merge k Sorted Lists

two methods are provided. The first one is like merge sort. The time complexity is T(k)=2T(k/2)+O(n*k), thus T(k)=O(nklogk).  The space complexity is the recursive stack O(logk).
The second one uses a minimum heap. Every node is read once. Every time we get the top node from the heap, we need to add  a  new one. So the time complexity is O(nklogk), which is the same as the first one. The space complexity is the size of the heap, which is O(k).

//first one

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty())
        {
            return NULL;
        }
           
        return mergeKLists2(lists,0,lists.size()-1);
   
    }  
    ListNode *mergeKLists2(vector<ListNode *> &lists,int start,int end) {
        if(start==end)
            return lists[start];
        return mergeTwoLists(mergeKLists2(lists,start,(start+end)/2),mergeKLists2(lists,(start+end)/2+1,end));
   
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0),*pre=&dummy;
        pre->next=l1;
        while(l1&&l2){
            if(l1->val>l2->val){
                ListNode*next=l2->next;
                l2->next=pre->next;
                pre->next=l2;
                l2=next;
            }
            else
                l1=l1->next;
            pre=pre->next;   
        }
        if(l2) pre->next=l2;
        return dummy.next;
    }

};

//second method, remember that the default priority_queue is maximum heap.

class Mycompare { public:     bool operator()(ListNode *a, ListNode *b) {         return a->val > b->val;     } }; class Solution { public:     ListNode *mergeKLists(vector<ListNode *> &lists) {         priority_queue<ListNode *, vector<ListNode *>, Mycompare> q;         for (int i = 0; i < lists.size(); ++i)             if (lists[i])                 q.push(lists[i]);         ListNode dummy(0), *cur = &dummy;         while (!q.empty()) {             ListNode *node = q.top();             q.pop();             cur = cur->next = node;             if (node->next)                 q.push(node->next);         }         return dummy.next;     } };