0023. 合并 K 个升序链表
题目地址（23. 合并 K 个排序链表）
题目描述
1
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
2
3
示例:
4
5
输入:
6
[
7
1->4->5,
8
1->3->4,
9
2->6
10
]
11
输出: 1->1->2->3->4->4->5->6
Copied!
前置知识
- 链表
- 归并排序
公司
- 阿里
- 百度
- 腾讯
- 字节
思路
- 1.这道题的数据结构是链表，那道是数组。这个其实不复杂，毕竟都是线性的数据结构。
- 2.这道题需要合并 k 个元素，那道则只需要合并两个。这个是两题的关键差别，也是这道题难度为
hard的原因。
因此我们可以看出，这道题目是
88.merge-sorted-array的进阶版本。其实思路也有点像，我们来具体分析下第二条。 如果你熟悉合并排序的话，你会发现它就是合并排序的一部分。具体我们可以来看一个动画
23.merge-k-sorted-lists
关键点解析
- 分治
- 归并排序(merge sort)
代码
代码支持 JavaScript， Python3, CPP
JavaScript Code：
1
/*
2
* @lc app=leetcode id=23 lang=javascript
3
*
4
* [23] Merge k Sorted Lists
5
*
6
* https://leetcode.com/problems/merge-k-sorted-lists/description/
7
*
8
*/
9
function mergeTwoLists(l1, l2) {
10
const dummyHead = {};
11
let current = dummyHead;
12
// l1: 1 -> 3 -> 5
13
// l2: 2 -> 4 -> 6
14
while (l1 !== null && l2 !== null) {
15
if (l1.val < l2.val) {
16
current.next = l1; // 把小的添加到结果链表
17
current = current.next; // 移动结果链表的指针
18
l1 = l1.next; // 移动小的那个链表的指针
19
} else {
20
current.next = l2;
21
current = current.next;
22
l2 = l2.next;
23
}
24
}
25
26
if (l1 === null) {
27
current.next = l2;
28
} else {
29
current.next = l1;
30
}
31
return dummyHead.next;
32
}
33
/**
34
* Definition for singly-linked list.
35
* function ListNode(val) {
36
* this.val = val;
37
* this.next = null;
38
* }
39
*/
40
/**
41
* @param {ListNode[]} lists
42
* @return {ListNode}
43
*/
44
var mergeKLists = function (lists) {
45
// 图参考： https://zhuanlan.zhihu.com/p/61796021
46
if (lists.length === 0) return null;
47
if (lists.length === 1) return lists[0];
48
if (lists.length === 2) {
49
return mergeTwoLists(lists[0], lists[1]);
50
}
51
52
const mid = lists.length >> 1;
53
const l1 = [];
54
for (let i = 0; i < mid; i++) {
55
l1[i] = lists[i];
56
}
57
58
const l2 = [];
59
for (let i = mid, j = 0; i < lists.length; i++, j++) {
60
l2[j] = lists[i];
61
}
62
63
return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
64
};
Copied!
Python3 Code：
1
# Definition for singly-linked list.
2
# class ListNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.next = None
6
7
class Solution:
8
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
9
n = len(lists)
10
11
# basic cases
12
if n == 0: return None
13
if n == 1: return lists[0]
14
if n == 2: return self.mergeTwoLists(lists[0], lists[1])
15
16
# divide and conqure if not basic cases
17
mid = n // 2
18
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))
19
20
21
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
22
res = ListNode(0)
23
c1, c2, c3 = l1, l2, res
24
while c1 or c2:
25
if c1 and c2:
26
if c1.val < c2.val:
27
c3.next = ListNode(c1.val)
28
c1 = c1.next
29
else:
30
c3.next = ListNode(c2.val)
31
c2 = c2.next
32
c3 = c3.next
33
elif c1:
34
c3.next = c1
35
break
36
else:
37
c3.next = c2
38
break
39
40
return res.next
Copied!
CPP Code:
1
class Solution {
2
private:
3
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
4
ListNode head(0), *tail = &head;
5
while (a && b) {
6
if (a->val < b->val) { tail->next = a; a = a->next; }
7
else { tail->next = b; b = b->next; }
8
tail = tail->next;
9
}
10
tail->next = a ? a : b;
11
return head.next;
12
}
13
public:
14
ListNode* mergeKLists(vector<ListNode*>& lists) {
15
if (lists.empty()) return NULL;
16
for (int N = lists.size(); N > 1; N = (N + 1) / 2) {
17
for (int i = 0; i < N / 2; ++i) {
18
lists[i] = mergeTwoLists(lists[i], lists[N - 1 - i]);
19
}
20
}
21
return lists[0];
22
}
23
};
Copied!
复杂度分析
- 时间复杂度：$O(kn*logk)$
- 空间复杂度：$O(logk)$
相关题目
扩展
这道题其实可以用堆来做，感兴趣的同学尝试一下吧。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago