题目
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 :
输入: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
思路
要将多个已按升序排列的链表合并成一个升序链表,可以使用分治法的思想。我们利用分治法的思想,递归地将链表数组拆分成两部分,然后合并这些部分,最终得到一个合并后的升序链表。
-
定义一个辅助函数mergeTwoLists(ListNode* list1, ListNode* list2),用于合并两个链表的方法,这是我们之前讨论过的合并两个升序链表的方法。
-
在mergeKLists函数中,首先判断输入的链表数组是否为空,如果为空则返回nullptr。
-
利用分治法的思想,将链表数组不断地拆分成两部分,然后递归地合并这些部分,直到只剩下一个链表为止。具体步骤如下:文章来源:https://www.toymoban.com/news/detail-834094.html
- 计算链表数组的中间位置mid,将链表数组拆分成两部分:左半部分为[0, mid-1],右半部分为[mid, size-1]。
- 递归调用mergeKLists函数,分别对左右两部分进行合并,得到leftList和rightList。
- 最终,再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表,并返回合并后的结果。
-
最终返回合并后的链表即可。文章来源地址https://www.toymoban.com/news/detail-834094.html
Code:
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
return merge(lists, 0, lists.size() - 1);
}
private:
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if (left == right) {
return lists[left];
}
if (left < right) {
int mid = left + (right - left) / 2;
ListNode* leftList = merge(lists, left, mid);
ListNode* rightList = merge(lists, mid + 1, right);
return mergeTwoLists(leftList, rightList);
}
return nullptr;
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
到了这里,关于LeetCode23.合并K个升序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!