合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解法1：挨个插入（笨方法）
将所有节点插入到第一个链表中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int i;
int n=lists.size();
if(n==0)
return NULL;
if(n==1)
return lists[0];
ListNode *p=new ListNode(-1);
for(i=1;i<n;i++)
{
p=lists[i];
ListNode *pm=new ListNode(-1);
ListNode *pa=new ListNode(-1);
pm=lists[0];
pa->next=lists[0];
while(p!=NULL&&pm!=NULL)
{
if(p->val<pm->val)
{
ListNode *temp=new ListNode(-1);
if(p->val<lists[0]->val)
{
temp=p;
p=p->next;
temp->next=lists[0];
lists[0]=temp;
pa=lists[0];
}
else
{
temp=p;
p=p->next;
temp->next=pm;
pa->next=temp;
pa=pa->next;
}
}
else
{
pm=pm->next;
pa=pa->next;
}
}
if(pm==NULL&&lists[0]!=NULL)
{
pa->next=p;
}
else if(pm==NULL&&lists[0]==NULL)
lists[0]=p;
}
return lists[0];
}
};
|
时间复杂度：KN
解法2：优先级队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
struct cmp
{
bool operator()(ListNode* l1, ListNode* l2)
{
return l1->val > l2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists){
ListNode* phead = new ListNode(0);
ListNode* p = phead;
if(lists.size() == 0)
return nullptr;
priority_queue<ListNode*, vector<ListNode*>, cmp> MinHeap;
for(int i = 0;i < lists.size();i++)
if(lists[i] != nullptr)
MinHeap.push(lists[i]);
while(!MinHeap.empty())
{
p->next = MinHeap.top();
p = p->next;
if(MinHeap.top()->next != nullptr)
MinHeap.push(MinHeap.top()->next);
MinHeap.pop();
}
return phead->next;
}
};
|
时间复杂度：NlogK