Merge K sorted lists -- Leetcode

Question:


Answer:
1. Using heap. O(k*n*logk).
class Solution {
private:
    struct cmp{
        bool operator()(ListNode* lhs, ListNode *rhs){
            if(lhs->val < rhs->val) return false;
            else return true;
        }
    };
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int K = lists.size();
        if (K == 0) return NULL;
        else if (K == 1) return lists[0];
       
        ListNode *listHead(NULL), *listRear(NULL);
        ListNode *node(NULL);
     
        priority_queue<ListNode*, vector<ListNode*>, cmp> h;
       
        // push K list heads into heap
        for(int i=0; i<K; ++i)
          if(lists[i] != NULL){
            h.push(lists[i]);
            lists[i] = lists[i]->next;
          }
           
        while(!h.empty()){
                   //pop the min of k nodes in the heap.
          node = h.top(); h.pop();
          if(node->next)
            h.push(node->next);
           
                   //insert node into new list.    
          if(listRear){
              listRear->next = node;
              listRear = listRear->next;
          }
          else{
              listHead = listRear = node;
          }
        }
       
        return listHead;
    }
};

2. Merge Lists using Divide and Conquer. O(k*n*logk).

1. public ListNode mergeKLists(ArrayList<ListNode> lists) {  
2.     if(lists==null || lists.size()==0)  
3.         return null;  
4.     return helper(lists,0,lists.size()-1);  
5. }  
6. private ListNode helper(ArrayList<ListNode> lists, int l, int r)  
7. {  
8.     if(l<r)  
9.     {  
10.         int m = (l+r)/2;  
11.         return merge(helper(lists,l,m),helper(lists,m+1,r));  
12.     }  
13.     return lists.get(l);  
14. }  
15. private ListNode merge(ListNode l1, ListNode l2)  
16. {   
17.     ListNode dummy = new ListNode(0);  
18.     dummy.next = l1;  
19.     ListNode cur = dummy;  
20.     while(l1!=null && l2!=null)  
21.     {  
22.         if(l1.val<l2.val)  
23.         {  
24.             l1 = l1.next;  
25.         }  
26.         else  
27.         {  
28.             ListNode next = l2.next;  
29.             cur.next = l2;  
30.             l2.next = l1;  
31.             l2 = next;  
32.         }  
33.         cur = cur.next;  
34.     }  
35.     if(l2!=null)  
36.         cur.next = l2;  
37.     return dummy.next;  
38. }