合并k个排序链表

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。
样例
给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here

        int n = lists.size();
        if (n == 0) {
            return NULL;
        }
        merge(lists,0,n-1);
        return lists[0];
    } 
    
   void merge(vector<ListNode *> &lists,int left,int right) {
       if(left == right) {
           return;
       }
       int mid = (left + right) / 2;
       merge(lists,left,mid);
       merge(lists,mid+1,right);
       ListNode *mergeList = mergeTwoList(lists[left],lists[mid+1]);
       lists[left]=mergeList;
   }
   
    ListNode *mergeTwoList(ListNode* list1,ListNode* list2) {
        if(list1==NULL) {
            return list2;
        } else if (list2==NULL){
            return list1;
        }
        ListNode* result;
        
        if(list1->val <= list2->val) {
            result = list1;
            result->next = mergeTwoList(list1->next,list2);
        } else {
            result =  list2;
            result->next = mergeTwoList(list2->next,list1);
        }
        
        return result;
    }
};

复杂度分析