☆打卡算法☆LeetCode 23、合并K个升序链表 算法解析
【摘要】 theme: arknights小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“将链表数组合并到一个升序链表中。”题...
theme: arknights
小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“将链表数组合并到一个升序链表中。”
题目链接:
来源:力扣(LeetCode)
链接:23. 合并K个升序链表 - 力扣(LeetCode) (leetcode-cn.com)
2、题目描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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 = [[]]
输出: []
二、解题
1、思路分析
这个题可以采用分治和递归的思路进行解决。
首先是分治,将k个链表分成k/2个链表组,两两合并,直到合并成一个链表。
然后用递归实现分治算法。
2、代码实现
代码参考:
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
if(lists == null || lists.Length == 0) {
return null;
}
return MergeKLists(lists, 0, lists.Length-1);
}
private ListNode MergeKLists(ListNode[] lists, int left, int right) {
if(left == right) {
return lists[left];
}
int mid = left + (right-left)/2;
ListNode l1 = MergeKLists(lists, left, mid);
ListNode l2 = MergeKLists(lists, mid+1, right);
return MergeTwoLists(l1, l2);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode dummy = new ListNode();
ListNode p1 = l1, p2 = l2, cur = dummy;
while(p1 != null && p2 != null) {
if(p1.val < p2.val) {
cur.next = p1;
cur = cur.next;
p1 = p1.next;
} else {
cur.next = p2;
cur = cur.next;
p2 = p2.next;
}
}
cur.next = p1 == null ? p2 : p1;
return dummy.next;
}
}
3、时间复杂度
时间复杂度 : O(n∗k∗logk)
其中链表数组长度为 k,链表的平均长度为 n。函数 MergeKLists 的时间复杂度为 O(k logk)(分治),函数 MergeTwoLists 的时间复杂度是 O(n),因此总的时间复杂度为 O(n∗k∗logk)。
空间复杂度: O(logk)
递归会使用到 O(logk) 空间代价的栈空间。
三、总结
结束条件:left == right
,即只剩下一个链表,无须合并,直接返回。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)