Leetcode 23 Merge k Sorted Lists
Leetcode 23 Merge k Sorted Lists
triplebee
发布于 2018-01-12 15:07:29
发布于 2018-01-12 15:07:29
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
标为hard难度的一道题，有点interesting，
题意为把K条有序的链表归并为一条有序的链表。
开始想也没想直接暴力n*k的复杂度，果不其然T了，数据出现了n=10000，k=10000的情况，不然怎么对得起hard难度呢？
下面是T掉的代码，
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* result=new ListNode(0);
ListNode* p=result;
while(lists.size()>0)
{
int pos=-1,minn=INT_MAX;
for(int i=0;i<lists.size();i++)
{
if(lists[i]==NULL)
{
lists.erase(lists.begin()+i);
i--; //删掉就不存在了，不能忘记下标减一
}
else if(lists[i]->val<minn)
{
minn=lists[i]->val;
pos=i;
}
}
if(pos==-1)
return result->next;
p->next=lists[pos];
p=p->next;
lists[pos]=lists[pos]->next;
}
return result->next;
}
};然后我开始思考，之前做过两个链表合并的题目
https://cloud.tencent.com/developer/article/1019324
合并两个链表的复杂度为O(n+m)，如果用在这题中，虽然合并次数将很多，但到后来会形成长链和短链的合并，
长链的最后一部分往往是直接接入的，因而实际的平均复杂度并不会很高，但具体是多少，也不太好分析。
这种想法在一般的情况下，应当是优于第一种做法的，
可是后来我想到，如果K个链表都只有一个元素，且随循环合并的方向递增，那么算法又将退化为第一种方法，n=10000，k=10000，随循环合并的方向递增的情况还是会超时。
算法会退化，其实很大程度上还是由于没有改变逐个合并的思路，如果采用分治的方法合并两个链表呢？
很显然，效果会好很多，n*k的复杂度将变为nlogK的复杂度。
/**
* 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)
{
ListNode* p=new ListNode(0);
ListNode* result=p;
while(l1 && l2)
{
ListNode* t=new ListNode(0);
p->next=t;
p=p->next;
if(l1->val<l2->val)
{
p->val=l1->val;
l1=l1->next;
}
else
{
p->val=l2->val;
l2=l2->next;
}
}
p->next=l1?l1:l2;
return result->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
while(lists.size()>1)
{
lists.push_back(mergeTwoLists(lists[0],lists[1]));
lists.erase(lists.begin());
lists.erase(lists.begin());
}
if(lists.size()==0)
return NULL;
return *(lists.begin());
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-09-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读