算法基础~链表~排序链表的合并（k条）
算法基础~链表~排序链表的合并（k条）
算法基础~链表~排序链表的合并（k条）
1，题意：已知k个已排序链表头结点指针，将这k个链表合并，合并后仍然为有序的，返回合并后的头结点。
2，方法之间时间复杂度的比较：
方法1（借助工具vector封装好的sort方法）：将k * n个结点放到vector，则原 vector的排序时间复杂度是 O(nlogn);
有k*n个结点的排序，时间复杂度是 O(knlog(kn));
方法2（分制后相连法），分制：这里咱要想到高中的DNA复制~一个DNA复制生成K个DNA的过程。
【1----复制----》k个数】，复制了n次，结果有k个数，则2n = k。
这里咱反过来，想到是在融合，则【k个数----复制----》1】，这个过程需要融合的次数，跟当初 复制次数一样，由2n = k，解得，n=logk。
●具体过程分析：
第一次，链表两两之间合并，进行 合并次数为 k/2,每次处理结点数字为2n个；
第二次，链表两两之间合并，进行 合并次数为 k/4,每次处理结点数字为4n个；
。。。
由上面推导的融合过程，知道最后一次，即 第 logk 次，链表两两之间进行 合并，进行合并次数为
k/2 logk,每次处理结点数字为2 logk n个；
时间复杂度：2n * k/2 + 4n * k/4 + 8n * k/8 + … + 2 logk n * k/2 logk = nk + nk + nk +… +nk = O(nklogk)；
所以方法2，更优；
3，从方法2的分析过程，咱深深的感受到一种：把规模大的问题变成规模较小的；规模较小的问题又变成规模更小的问题，
小到一定程度可以直接得出它的解，从而得到问题的解。~没错，是递归的味道！
4，直接上代码，分析如上【代码中的mergeTwoLists（链表1头指针，链表2头指针）参考咱上一篇文章：
《算法基础~链表~排序链表的合并（2条）》~ https://www.cnblogs.com/shan333/p/15041561.html】：
public class Solution { public:
ListNode* mergeKLists(std::vector<ListNode*>& lists){ if(lists.size() == 0){ return NULL;
} if(lists.size() == 1){ return lists[0];
} if(lists.size() == 2){ return mergeTwoLists(lists[0],lists[1]);
} int mid = lists.size() / 2; //拆分成两个子lists
std::vector<ListNode*> sub1_lists;
std::vector<ListNode*> sub2_lists; for(int i = 0; i < mid; i++){
sub1_lists.push_back(lists[i]);
} for(int i = mid; i < lists.size(); i++){
sub2_lists.push_back(lists[i]);
} //递归，不断的两两链表进行融合
ListNode *l1 = mergeKList(sub1_lists);
ListNode *l2 = mergeKList(sub2_lists); return mergeTwoLists(l1, l2);
}
}
5，递归思想的使用：
递归算法的思想是：把规模大的问题变成规模较小的；规模较小的问题又变成规模更小的问题，小到一定程度可以直接得出它的解，从而得到问题的解。
解决问题时，把一个问题转化为一个新的问题，而这个新的问题的解决方法仍与原问题的解法相同，
只是所处理的对象有所不同，这些被处理的对象之间是有规律的递增或递减；
来源https://www.cnblogs.com/shan333/p/15042105.html