problem：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
先合并两个list，再根据归并排序的方法递归合并。假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。空间复杂度的话是递归栈的大小O(logk)。
/**
* 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) // 将两个list merge
{
if(!l1)
return l2;
if(!l2)
return l1;
ListNode *tmp = new ListNode();
ListNode *ans = tmp;
while(l1 && l2)
{
if(l1 -> val < l2 -> val)
{
ans -> next = l1;
ans = ans -> next;
l1 = l1 -> next;
}
else
{
ans -> next = l2;
ans = ans -> next;
l2 = l2 -> next;
}
}
if (l1)
{
while(l1)
{
ans -> next = l1;
ans = ans -> next;
l1 = l1 -> next;
}
} if (l2)
{
while(l2)
{
ans -> next = l2;
ans = ans -> next;
l2 = l2 -> next;
}
}
ans = tmp;
delete ans;
return tmp -> next;
}
ListNode *reMerge(vector<ListNode *> &lists, int l, int r)
{
if(l < r) // 类似于归并排序，把一大块分成l和r两块，然后将两个合并（l和r也还可以再分）
{
int m = (l + r)/;
return mergeTwoLists(reMerge(lists, l, m), reMerge(lists, m + , r));
}
else
return lists[l];
}
ListNode *mergeKLists(vector<ListNode *> &lists)
{
ListNode *ans = NULL;// 用NULL 而不是利用 new ListNode(0)
if (lists.size() == )
return ans;
return reMerge(lists, , lists.size() - );
}
};