Merge k Sorted Lists

编号 : 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 |

从表中结果可以看出，测试集中，链表的总个数较多，但是出现的值的种数很少。