k个排序链表的合并
LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的，返 回合并后的头节点。
思考与分析
最普通的方法，k个链表按顺序合并k-1次，暴力的进行合并。 设有k个链表，平均每个链表有n个节点，时间复杂度: (n+n)+(2n+n)+((k-1)n+n) = (1+2+...+k-1)n +(k-1)n =(1+2+...+k)n-n=(k^2+k-1)/2 * n = O(k^2*n)
是否与更好的方法?
方法1
将kn个节点放到vector中，再将vector排序，再将节点顺序相连。 设有k个链表，平均每个链表有n个节点，时间复杂度: kNlogkN + kN = O(kN*logkN) (比如k=100, n = 10000) logkN = 20， k = 100
#include<vector>
#include<algorithm>
bool cop(const ListNode *a, const ListNode *b){
return a->val < b-> val;
}
int main(){
ListNode a(3);
ListNode b(2);
ListNode c(5);
ListNode d(0);
std::vector<ListNode *> node_vec;
node_vec.push_back(&a);
node_vec.push_back(&b);
node_vec.push_back(&c);
node_vec.push_back(&d);
std::sort(node_vec.begin(), node_vec.end(),cmp);
for(int i = 0; i < node_vec.size(); i++){
printf("%d\n",node_vec[i]->val);
}
return 0;
}#include<vector>
#include<algorithm>
bool cmp(const ListNode *a, const ListNode *b){
return a->val < b->val;
}
class Solution{
public:
ListNode * mergeKList(std::vector<ListNode*>& lists){
std::vector<ListNode *>node_vec;
for(int i = 0; i < lists.size();i++){
ListNode *head = list[i];
while(head){
node_vec.push_back(head);
head = head->next;
}
if( node_vec.size() ==0){
return NULL;
}
std::sort(node_vec.begin(),node_vec.end(),cmp);
for(int i =1; i < node_vec.size(); i++){
node_vec[i-1]->next = node_vec[i];
}
node_vec[node_vec.size()-1]->next = NULL;
return node_vec[0];
}
}
};方法二 分制归并
对k个链表使用分制的思想，两两进行合并。 设有k个链表，平均每个链表有n个节点，时间复杂度: 第1轮，进行k/2次，每次处理2n个数字;第2轮，进行k/4次，每次处理4n个数字;...; 最后一次，进行k/(2logk)次，每次处理2logkN个值。 2Nk/2 + 4N * k/4 + 8N * k/8 +...+2^logk * N * k/(2^logk) =Nk + Nk +...+Nk = O(kNlogk)
ListNode *mergeKList(std::vector<ListNode*> &lists){
if lists.size() == 0){
return NULL;
}
if(lists.size() == 1){
return list[0];//如果只有一个list，直接返回头节点
}
if(lists.size() == 2){
return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.size() / 2;
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 = mergeKLists(sub1_lists);
ListNode *l2= mergeKLists(sub2_lists);
return mergeTwoList(l1,l2);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.04.29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录