Merge sort, merge lists problems

1. Merge k Sorted Lists [leetcode]

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

Solution:  This problem was labelled "hard", but probably it is a medium level.
My first code was to compare lists front every time and did not pass. Then I realized I did not have to compare all every time. A heap will save the job. 
If average length of list is n, # of lists is k, then the complexity is O(n*k*lg(k)) (suppose heap an new element is o(log), which is usually true). Then it passed. 


    class Compare
    {
    public:
        bool operator() (ListNode*a, ListNode*b)
        {
               return a->val>b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return 0;
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        for (auto &ls: lists){
            if (ls) pq.push(ls);
        }
        
        if (pq.empty()) return nullptr;
        ListNode dummy(0);
        ListNode*cur, *head=&dummy;
        
        while(!pq.empty()){
            cur= pq.top(); pq.pop();
            if (cur->next) pq.push(cur->next);
            head->next=cur;
            head=cur;
        }
        return dummy.next;
    }

2. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Solution: nothing more to say, see 
http://charleshuboston.blogspot.com/2015/11/sort-linked-list-in-on-log-n-time-o1.html

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        //l1 and l2 have nodes
        ListNode*ret ;
        if (l1->val<l2->val){
            ret=l1;
            while (l1->next && l1->next->val<l2->val){
                   l1=l1->next;
            }
            ListNode*l1next= mergeTwoLists(l1->next, l2);
            l1->next=l1next;
            
        }else{
            ret=l2;
            while (l2->next && l2->next->val<=l1->val){
                   l2=l2->next;
            }
            ListNode*l2next= mergeTwoLists(l1, l2->next);
            l2->next=l2next;
        } 
        return ret;

    }

3 Merge Sorted Array[leetcode]

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
     int pm=m-1, pn=n-1;     
     while (pm>=0 && pn>=0)  
           nums1[pm+pn+1]=nums1[pm]>nums2[pn]?  nums1[pm--]:nums2[pn--]; 

     if (pn==-1) return;
     //copy nums2 remains to nums1
     if (pm==-1) 
         for (int i=0; i<=pn; ++i)
            nums1[i]=nums2[i];
    }