合并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;
}
};
