题目来源
23. 合并 K 个升序链表 - 力扣（LeetCode）
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例
示例 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
题目解析
本题是 LeetCode - 21 合并两个有序链表-CSDN博客 进阶题。
本题最简单的解题思路是：
若 lists 非空，则以 lists[0] 作为基链表 base，然后从索引 1 开始遍历 lists 的每一个元素 lists[i]，依次和 base 合并，这里 lists[i] 和 base 的合并可以套用 leetcode 21逻辑。
但是这种顺序遍历合并的时间复杂度偏高。
为了降低时间复杂度，我们可以使用分治的思路，下面画个图来对比下顺序和分治的区别：
顺序合并图示如下：
分治合并图示如下：
由于我们目前无法直接合并 K=5 个链表，即无法直接合并 [0, 4] 范围的链表，此时可以进行范围分治，将大问题分解为相同的、但是规模更小的多个子问题。
比如 [0, 4] 范围的合并结果：等价于下面两个子范围合并结果的二次合并结果
这里对大范围进行二分，即先找 [L,R] 中间点 mid，然后分解为 [L,mid] 和 [mid+1,R]
- [0,2] 范围
- [3,4] 范围
那么 [0, 4] 范围的链表合并问题，就分解为了求解 [0,2] 范围链表合并、以及 [3,4] 范围链表合并。
接下来可以对子问题继续分治，比如 [0,2] 范围可以分解为：
- [0,1] 范围
- [2,2] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[2] 链表
接下来可以对子问题继续分治，比如 [0,1] 范围可以分解为：
- [0,0] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[0] 链表
- [1,1] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[1] 链表
当子问题无法继续分治时，即分解到了最小规模子问题时（比如范围内只有一个链表），此时可以进行回溯
- 由于 [0,0]、[1,1] 范围无法继续分治，因此它们是最小规模子问题，可以直接求解范围内链表合并结果分别为 lists[0]、lists[1]，我们假设 lists[0] 和 lists[1] 的合并结果为 a 链表，那么 [0,1] 范围的合并结果就是 a。
- 由于已知 [0,1] 的合并结果 a，而 [2,2] 范围已经时最小规模子问题（其合并结果为 lists[2]），那么 [0,2] 范围的合并结果即为 a 和 lists[2] 的合并结果，假设为 b
同理，我们可以按照上面逻辑，求解出 [3,4] 范围的合并结果，假设为 c
那么，最终 [0,4] 范围的合并结果，即为 b 和 c 的合并结果。
C源码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* dummy_head =(struct ListNode*)malloc(sizeof(struct ListNode));dummy_head->val = 0;dummy_head->next = NULL;struct ListNode* tail = dummy_head;while (list1 != NULL && list2 != NULL) {if (list1->val < list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}tail->next = list1 != NULL ? list1 : list2;return dummy_head->next;
}// 将 lists 的 [l, r] 范围的链表 合并为 一个链表
struct ListNode* merge(struct ListNode** lists, int l, int r) {if (l == r) { // 如果只有一个链表，则直接返回对应链表return lists[l];}int mid = (l + r) / 2;// 分治struct ListNode* list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表struct ListNode* list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表// 合并两个有序链表return mergeTwoLists(list1, list2);
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0) {return NULL;}return merge(lists, 0, listsSize - 1);
}C++源码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) {return nullptr;}return merge(lists, 0, lists.size() - 1);}// 将 lists 的 [l, r] 范围的链表 合并为 一个链表ListNode* merge(vector<ListNode*>& lists, int l, int r) {if (l == r) { // 如果只有一个链表，则直接返回对应链表return lists[l];}int mid = (l + r) / 2;// 分治ListNode* list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表ListNode* list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表// 合并两个有序链表return mergeTwoLists(list1, list2);}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy_head = new ListNode(0, nullptr);ListNode* tail = dummy_head;while (list1 != nullptr && list2 != nullptr) {if (list1->val < list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}tail->next = list1 != nullptr ? list1 : list2;return dummy_head->next;}
};Java源码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}return merge(lists, 0, lists.length - 1);}// 将 lists 的 [l, r] 范围的链表 合并为 一个链表public ListNode merge(ListNode[] lists, int l, int r) {if (l == r) { // 如果只有一个链表，则直接返回对应链表return lists[l];}int mid = (l + r) / 2;// 分治ListNode list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表ListNode list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表// 合并两个有序链表return mergeTwoLists(list1, list2);}public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy_head = new ListNode(0, null);ListNode tail = dummy_head;while (list1 != null && list2 != null) {if (list1.val < list2.val) {tail.next = list1;list1 = list1.next;} else {tail.next = list2;list2 = list2.next;}tail = tail.next;}tail.next = list1 != null ? list1 : list2;return dummy_head.next;}
}Python源码实现
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def mergeKLists(self, lists):""":type lists: List[Optional[ListNode]]:rtype: Optional[ListNode]"""if len(lists) == 0:return None# 将 lists 的 [l, r] 范围的链表 合并为 一个链表def merge(l, r):if l == r: # 如果只有一个链表，则直接返回对应链表return lists[l]mid = (l + r) // 2# 分治list1 = merge(l, mid) # 将 lists 的 [l, mid] 范围链表 合并为 一个链表list2 = merge(mid + 1, r) # 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表# 合并两个有序链表return self.mergeTwoLists(list1, list2)return merge(0, len(lists) - 1)def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""dummy_head = ListNode(0, None)tail = dummy_headwhile list1 != None and list2 != None:if list1.val < list2.val:tail.next = list1list1 = list1.nextelse:tail.next = list2list2 = list2.nexttail = tail.nexttail.next = list1 if list1 else list2return dummy_head.next
JavaScript源码实现
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val = (val===undefined ? 0 : val)* this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode[]} lists* @return {ListNode}*/
var mergeKLists = function (lists) {if (lists.length == 0) {return null;}return merge(lists, 0, lists.length - 1);
};// 将 lists 的 [l, r] 范围的链表 合并为 一个链表
var merge = function (lists, l, r) {if (l == r) { // 如果只有一个链表，则直接返回对应链表return lists[l];}const mid = (l + r) >> 1;// 分治const list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表const list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表// 合并两个有序链表return mergeTwoLists(list1, list2);
}var mergeTwoLists = function (list1, list2) {const dummy_head = new ListNode(0, null);let tail = dummy_head;while (list1 != null && list2 != null) {if (list1.val < list2.val) {tail.next = list1;list1 = list1.next;} else {tail.next = list2;list2 = list2.next;}tail = tail.next;}tail.next = list1 != null ? list1 : list2;return dummy_head.next;
};
