题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析
合并k个有序链表。
我们从数据结构的链表章节学会了如何合并两个链表，针对此题，一个简单的解法便是遍历k次，两个链表合并，合并后的结果与下一个链表合并；
此时时间复杂度为O(nk)，遗憾，提交会出现TLE。
所以，必须另觅他法，我们知道排序领域中很多方法都可以提高性能比如合并排序性能为O(nlogn)；可以应用到此题，可以顺利AC，时间复杂度为O(nlogk)
AC代码
class Solution {
public:
/*方法一：采用合并排序的思路 复杂度为O(nlogk)*/
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
ListNode *head = NULL;
if (len == 0)
return head;
else if (len == 1)
{
head = lists[0];
return head;
}
else{
int mid = (len - 1) / 2;
vector<ListNode *> l1(lists.begin(), lists.begin() + mid + 1);
vector<ListNode *> l2(lists.begin() + mid + 1, lists.end());
ListNode *head1 = mergeKLists(l1);
ListNode *head2 = mergeKLists(l2);
return mergeTwoLists(head1, head2);
}//else
}
/*方法二：暴力法 复杂度为O(nK) 出现超时*/
ListNode* mergeKLists2(vector<ListNode*>& lists) {
int len = lists.size();
ListNode *head = NULL;
if (len == 0)
return head;
else if (len == 1)
{
head = lists[0];
return head;
}
else{
head = mergeTwoLists(lists[0], lists[1]);
for (int i = 2; i < len; i++)
head = mergeTwoLists(head, lists[i]);
}
return head;
}
/*合并两个链表函数*/
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
//合并后链表初始化为空
ListNode *rl = NULL;
ListNode *p = l1, *q = l2;
if (l1->val <= l2->val)
{
rl = l1;
p = l1->next;
}
else{
rl = l2;
q = l2->next;
}
rl->next = NULL;
ListNode *head = rl;
while (p && q)
{
if (p->val <= q->val)
{
rl->next = p;
p = p->next;
}
else{
rl->next = q;
q = q->next;
}//else
rl = rl->next;
}//while
while (p)
{
rl->next = p;
p = p->next;
rl = rl->next;
}
while (q)
{
rl->next = q;
q = q->next;
rl = rl->next;
}
return head;
}
};