Merge k Sorted Lists

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

如果直接遍历链表数组，时间复杂度为T(n)=T(n-1)+o(lenn);即合并前n-1个链表的时间+与第n个链表长度

可以采用归并的思路来做，时间复杂度为T(n) = 2T(n/2) + o(totalLen);

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
    {
        if(l1==NULL){
            return l2;
        }
        if(l2==NULL){
            return l1;
        }
        ListNode* head = l1->val<l2->val? l1:l2;
        if(head==l1){
            head->next = mergeTwoLists(l1->next,l2);
        }else{
            head->next = mergeTwoLists(l1,l2->next);
        }
        return head;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists,int start,int end)
    {
        if(start >= end){
            return NULL;
        }
        if(start+1==end){
            return lists[start];
        }
        int mid = start + (end-start)/2 ;
        ListNode* l1 = mergeKLists(lists,start,mid);
        ListNode* l2 = mergeKLists(lists,mid,end);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int listsSize = lists.size();
        return mergeKLists(lists,0,listsSize);
    }
};