1.问题描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
2.难度等级
Hard。
3.热门指数
★★★★☆
4.解题思路
方法一:顺序合并
我们可以想到一种最朴素的方法,依次将链表数组中的链表与最终结果合并。问题便退化成合并两个有序链表。
如何合并两个有序链表呢?
遍历两个链表选择值较小的结点链接到结果链表中即可。当一个节点被添加到结果链表之后,将对应链表中的节点向后移一位。
为了简化对结果链表边界条件的判断,可以引入哨兵结点。哨兵结点的 Next 指针便是结果链表的头结点。
遍历 list1 或 list2 链表,选择 list1 与 list2 链表当前结点值较小的结点,挂接到结果链表,并将较小结点后移一位。
如果有一个为空,结束遍历,则将未遍历完的链表,直接挂接到结果链表。
时间复杂度: 假设每个链表的最长长度是 n。在第一次合并后,结果链表的长度为 n;第二次合并后,结果链表的长度为 2n,第 i 次合并后,结果链表的长度为 in。第 i 次合并的时间代价是 O(n+(i−1)×n)= O(in),那么总的时间代价为
O
(
∑
i
=
1
k
(
i
×
n
)
)
=
O
(
(
1
+
k
)
⋅
k
2
×
n
)
=
O
(
k
2
n
)
O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n)
O(i=1∑k(i×n))=O(2(1+k)⋅k×n)=O(k2n)
故渐进时间复杂度为
O
(
k
2
n
)
O(k^2n)
O(k2n),其中 k 为链表个数。
空间复杂度: 没有用到与 k 和 n 规模相关的辅助空间,故渐进空间复杂度为 O(1)。
下面以 Golang 为例给出实现。
func merge(head1, head2 *ListNode) *ListNode {
dummyHead := &ListNode{}
temp, temp1, temp2 := dummyHead, head1, head2
for temp1 != nil && temp2 != nil {
if temp1.Val < temp2.Val {
temp.Next = temp1
temp1 = temp1.Next
} else {
temp.Next = temp2
temp2 = temp2.Next
}
temp = temp.Next
}
if temp1 != nil {
temp.Next = temp1
} else {
temp.Next = temp2
}
return dummyHead.Next
}
func mergeKLists(lists []*ListNode) *ListNode {
var head *ListNode
for _, l := range lists {
head = merge(head, l)
}
return head
}
方法二:分治合并
可以优化方法一,采用分治的方法进行合并。
- 将 k 个链表配对并将同一对中的链表合并;
- 第一轮合并以后, k 个链表被合并成了
k
2
\frac{k}{2}
2k个链表,然后是
k
4
\frac{k}{4}
4k 个链表,
k
8
\frac{k}{8}
8k 个链表等等。
重复这一过程,直到我们得到了最终的有序链表。 - 重复这一过程,直到我们得到最终的有序链表。
时间复杂度: 考虑递归「向上回升」的过程,每一轮合并的时间复杂度都是 O(kn),需要合并 logk 轮,所以总的时间复杂度是 O(kn*logk)。
空间复杂度: 递归会使用到 O(logk) 空间代价的栈空间。
下面以 Golang 为例给出实现。
func merge(head1, head2 *ListNode) *ListNode {
dummyHead := &ListNode{}
temp, temp1, temp2 := dummyHead, head1, head2
for temp1 != nil && temp2 != nil {
if temp1.Val < temp2.Val {
temp.Next = temp1
temp1 = temp1.Next
} else {
temp.Next = temp2
temp2 = temp2.Next
}
temp = temp.Next
}
if temp1 != nil {
temp.Next = temp1
} else {
temp.Next = temp2
}
return dummyHead.Next
}
func divideMerge(lists []*ListNode, l, r int) *ListNode {
if l == r {
return lists[l]
}
mid := (l + r) / 2
// 合并左链表
lhead := divideMerge(lists, l, mid)
// 合并右链表
rhead := divideMerge(lists, mid+1, r)
// 合并左右链表
return merge(lhead, rhead)
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
return divideMerge(lists, 0, len(lists)-1)
}
方法三:使用优先队列合并
这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,kkk 个链表就最多有 kkk 个满足这样条件的元素,每次在这些元素里面选取 val\textit{val}val 属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。
时间复杂度: 考虑优先队列中的元素不超过 k 个,那么插入和删除的时间代价为 O(logk),这里最多有 kn 个结点,对于每个结点都被插入删除各一次,故总的时间代价为 O(kn*logk)。
**空间复杂度:**这里用了优先队列,优先队列中的元素不超过 k 个,故渐进空间复杂度为 O(k)。
下面以 C++ 为例给出实现。文章来源:https://www.toymoban.com/news/detail-805331.html
class Solution {
public:
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
参考文献
23. 合并K 个升序链表 - LeetCode文章来源地址https://www.toymoban.com/news/detail-805331.html
到了这里,关于合并K个升序链表(LeetCode 23)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!