合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
思路
我们可以想到一种最朴素的方法：用一个变量
\textit{ans}
来维护以及合并的链表，第
i
次循环把第
i
个链表和
\textit{ans}
合并，答案保存到
\textit{ans}
中。
代码
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};
复杂度分析
时间复杂度：假设每个链表的最长长度是
n
。在第一次合并后，
\textit{ans}
的长度为
n
；第二次合并后，
\textit{ans}
的长度为
2\times n
，第
i
次合并后，
\textit{ans}
的长度为
i\times n
。第
i
次合并的时间代价是
O(n + (i - 1) \times n) = O(i \times n)
，那么总的时间代价为
O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n)
，故渐进时间复杂度为
O(k^2 n)
。
空间复杂度：没有用到与
k
和
n
规模相关的辅助空间，故渐进空间复杂度为
O(1)
。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读