LeetCode 23. 合并K个排序链表

清欢

August 11, 2020

285views

No comments

1730 words

LeetCode 算法

困难

## 题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

```text
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
```

## 思路

将每个链表的头部记录在 set 中，并做好 head 的值与 链表 index 的映射。每次从 set 取出链表中最小的头部 value，去 map 中查询出等值的链表 index（使用 queue 保存），依次将链表元素取出。边界是当 set 中不存在元素时所有链表取完。

## 代码

```C++
struct ListNode {
    int val;
    ListNode *next;

ListNode(int x) : val(x), next(NULL) {}
};

set<int> miniSet;
map<int, queue<int>> valueIndexMapper;

ListNode *mergeKLists(vector<ListNode *> &lists) {
 ListNode *head = new ListNode(0), *tmp = head;
 for (int i = 0; i < lists.size(); ++i) {
 if (lists[i] != nullptr) {
 valueIndexMapper[lists[i]->val].push(i);
 miniSet.insert(lists[i]->val);
 }
 }
 while (miniSet.size() > 0) {
 int miniNow = *miniSet.begin();
 queue<int> q = valueIndexMapper[miniNow];
 while (!q.empty()) {
 int index = q.front();
 ListNode *item = lists[index];
 lists[index] = lists[index]->next;
 tmp->next = item;
 tmp = tmp->next;
 while (item->next != NULL && item->next->val == miniNow) {
 item = lists[index];
 lists[index] = lists[index]->next;
 tmp->next = item;
 tmp = tmp->next;
 }
 if(item->next != NULL){
 miniSet.insert(item->next->val);
 valueIndexMapper[item->next->val].push(q.front());
 }
 q.pop();
 }
 miniSet.erase(miniNow);
 }
 return head->next;
}
```

![leetcode-cn-23.png][1]

[1]: http://alomerry.com/usr/uploads/2020/08/3354624359.png<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal">版权属于：清欢本文链接：<a class="content-copyright" href="http://alomerry.com/archives/403/">http://alomerry.com/archives/403/</a>转载时须注明出处及本声明</blockquote>

Last modification：August 11th, 2020 at 07:12 pm

觉得我的文章有帮助吗，欢迎赞赏呀(๑• . •๑)

LeetCode 23. 合并K个排序链表