Merge k Sorted Lists
LeetCode笔记 阅读(70)
编号 : 23
难度 : <font color="red">Hard</font>
# 题目 :
>Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
>
>**Example**:
>>**Input**:
>>```
>>[
>> 1->4->5,
>> 1->3->4,
>> 2->6
>>]
>>```
>>**Output**: 1->1->2->3->4->4->5->6
>
# 解 :
```Cpp
/**
* 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 preHead(0); // 为了方便，preHead.next指向返回链表的头节点
ListNode* pos = &preHead; // 指示链表的尾，方便添加节点
int k = lists.size();
while(true)
{
/* 查找剩余节点里最小的节点 */
ListNode** select = nullptr; // 采用二级指针，方便从移动
for(int i = 0; i < k; i++)
{
if((select == nullptr && lists[i] !=nullptr)
|| (select != nullptr && lists[i] !=nullptr && (*select)->val > lists[i]->val)
)
{
select = &lists[i];
}
}
if(select == nullptr)
{
// 所有链表的所有节点都已经遍历完了
break;
}
else
{
pos->next = *select; // 将找到的最小节点赋给pos->next
*select =(*select)->next; // 将select向后移，本质上是将list[i]向后移，即删除该节点
pos = pos->next;
}
}
return preHead.next;
}
};
```
# 分析 :
这道题要求将`k`个升序的链表合并为一个。
上述解法创建一个新的链表，并从输入的各个链表的顶部挑选最的小节点，将该节点插入新链表并从原链表中移除，直到所有节点都处理完为止。
这个解法非常的慢，内层的`for`循环的时间复杂度是`O(k)`，其中`k`为输入的链表的个数。
外层的`while`循环每次处理一个节点，直到所有节点都处理完，复杂度为`O(n)`，其中`n`为节点总个数。
所以循环嵌套的总时间复杂度为`O(k*n)`，`k`为链表个数，`n`为节点总个数
## 更快的办法
```Cpp
/**
* 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) {
map<int, int> buffer; // buffer保存各个值出现的次数
int k = lists.size();
if(k == 0)
{
return nullptr;
}
ListNode preHead(0); // 为了方便，preHead.next指向返回链表的头节点
ListNode* pos = &preHead; // 指示链表的尾，方便添加节点
/* 遍历各个节点，保存各个值出现的个数 */
for(int i = 0; i < k; i++)
{
for(ListNode* lp = lists[i]; lp != nullptr; lp = lp->next)
{
if(buffer.find(lp->val) == buffer.end())
{
buffer[lp->val] = 1;
}
else
{
buffer[lp->val] += 1;
}
}
}
/* std::map是按key升序的 */
for(auto& pair : buffer)
{
/* 根据值出现的次数,相应的插入节点 */
for(int i = 0; i < pair.second; i++)
{
pos->next = new ListNode(pair.first);
pos = pos->next;
}
}
return preHead.next;
}
};
```
这个方法遍历全部节点（复杂度为`O(n)`，其中`n`是节点总个数）使用`std::map`保存所有节点中各个值出现的次数。
然后遍历该`map`（复杂度为`O(mlogm)`，其中`m`是值的种数`），根据各个值出现的次数插入相应数量的节点。
故总的复杂度为`O(n + mlogm)`，其中`n`是节点的总个数，`m`是值的种数。
> 这里利用到了`std::map`有序的特性，它的查找复杂度为`O(logn)`，`n`是元素个数。
## 分治法
```Cpp
/**
* 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) {
if(lists.size() == 0)
{
return nullptr;
}
/* 分治 */
while(lists.size() > 1)
{
lists.push_back(mergeTwoLists(lists[0], lists[1]));
lists.erase(lists.begin());
lists.erase(lists.begin());
}
return lists[0];
}
/* 合并两个链表 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
ListNode preHead(0); // 为了方便，preHead.next指向返回链表的头节点
ListNode* pos = &preHead; // 指示链表的尾，方便添加节点
while(l1 != nullptr || l2 != nullptr)
if(l1 == nullptr)
{
pos->next = l2;
l2 = nullptr;
}
else if(l2 == nullptr)
{
pos->next = l1;
l1 = nullptr;
}
else if(l1->val < l2->val)
{
pos->next = new ListNode(l1->val);
pos = pos->next;
l1 = l1->next;
}
else
{
pos->next = new ListNode(l2->val);
pos = pos->next;
l2 = l2->next;
}
return preHead.next;
}
};
```
这个解法将输入的链表两两合并，直到最终合并为一个链表。
合并两个链表的方法和最开始合并`k`个的方法一样，所以合并两个链表的复杂度为`O(m)`，其中`m`是两个链表的元素总个数，`m <= n`，`n`为全部链表的元素总个数。
两两合并到最终成为一个链表需要合并`logk`次，故复杂度为`O(logk)`，其中`k`是输入链表的总个数。
故整个算法的时间复杂度为`O(nlogk)`，其中`n`为节点的总个数，`k`为链表的个数。
## 效率对比
| 方案 | Runtime | Memory |
| :-: | :-: | :-: |
| O(k*n) | 460 ms | 10.7 MB |
| O(n + mlogm) | 24 ms | 11.6 MB |
| O(nlogk) | 264 ms | 16.3 MB |
从表中结果可以看出，测试集中，链表的总个数较多，但是出现的值的种数很少。