合并两个及以上有序链表问题
2023-02-18 16:36:38 时间
合并两个及以上有序链表问题
作者:Grey
原文地址:
题目一:合并两个有序链表
题目一思路
设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头。
首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以。
这样,我们就设置好了要返回链表的头节点,假设头节点是head,
依次移动t1和t2指针,谁小,谁就接入进来。依次操作,直到两个链表都遍历完毕为止。
此外,有个显而易见的结论:如果l1和l2有一个链表为空,则返回那个不为空的链表即可
题目一完整代码
public class LeetCode_0021_MergeTwoSortedLists {
public static class ListNode {
public int val;
public ListNode next;
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
// 如果任何一个链表为空,那么直接返回另外一个链表即可
return l1 == null ? l2 : l1;
}
// 谁小谁作为头
ListNode head = l1.val > l2.val ? l2 : l1;
// t1 和 t2 表示l1和l2下一个要遍历的位置
ListNode t1 = head == l1 ? l1.next : l1;
ListNode t2 = head == l2 ? l2.next : l2;
ListNode cur = head;
while (t1 != null || t2 != null) {
if (t1 == null) {
// l1链表已经到头,剩下只需要把l2链表接入进来即可
cur.next = t2;
t2 = t2.next;
cur = cur.next;
continue;
}
if (t2 == null) {
// l2链表已经到头,剩下只需要把l2链表接入进来即可
cur.next = t1;
t1 = t1.next;
cur = cur.next;
continue;
}
// l1和l2都没有到头,那么谁小谁接入进来即可。
if (t1.val > t2.val) {
cur.next = t2;
t2 = t2.next;
} else {
cur.next = t1;
t1 = t1.next;
}
cur = cur.next;
}
return head;
}
}
题目二:合并多个有序链表
题目二关键思路
准备一个小根堆,并把每个链表的头节点加入到小根堆中,此时,小根堆堆顶弹出的节点一定是最后生成链表的头节点。
假设链表为:L1,L2...LN
第一步,先将L1,L2...LN的头节点L1H,L2H...LNH加入小根堆
第二步,从小根堆堆顶弹出一个元素,作为最后链表的头节点。
第三步,第二步中弹出节点所在的链表假设是i号链表,那么就找弹出节点的下一个位置(假设为X)再和小根堆堆顶元素比较:
如果X比堆顶元素大,则堆顶元素弹出,X进入小根堆
如果X比堆顶元素小,则直接不需要进入堆顶,作为结果链表
题目二完整代码
public class LeetCode_0023_MergeKSortedLists {
public static class ListNode {
int val;
ListNode next;
}
public static ListNode mergeKLists(ListNode[] lists) {
if (null == lists || lists.length == 0) {
return null;
}
if (1 == lists.length) {
return lists[0];
}
// 小根堆
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
for (ListNode list : lists) {
if (null != list) {
queue.add(list);
}
}
ListNode res = queue.poll();
ListNode head = res;
while (!queue.isEmpty()) {
if (res != null) {
ListNode n = res.next;
if (n == null) {
res.next = queue.poll();
res = res.next;
} else if (n.val > queue.peek().val) {
res.next = queue.poll();
res = res.next;
queue.add(n);
} else {
res = res.next;
}
}
}
return head;
}
}
更多
相关文章
- 记一次 .NET 某桌面奇侠游戏 非托管内存泄漏分析
- Prometheus搭乘华为云GaussDB(for Influx):让监控数据更安全
- 数仓如何设置大小写不敏感函数
- 实践丨SpringBoot整合Mybatis-Plus项目存在Mapper时报错
- 从HDFS的写入和读取中,我发现了点东西
- 加快云原生技术转型, 智能调度登陆华为云DevOps: 增速,节源
- 性能指标、响应时间、并发量…聊聊性能优化的衡量指标
- 平衡树:为什么Redis内部实现用跳跃表
- TypeScript里string和String,真不是仅仅是大小写的区别
- 【OpenHarmony移植案例与原理】XTS子系统之应用兼容性测试用例开发
- 华为云发布实时音视频行业加速器,为企业解决技术与商业双重难题
- grpc双向流究竟是什么情况?2段代码告诉你
- 你了解部署流水线吗?
- 昇腾CANN论文上榜CVPR,全景图像生成算法交互性再增强!
- presto是如何保证作业内存不会发生冲突和溢出
- OpenHarmony移植:XTS子系统之应用兼容性测试套件
- 云图说|DRS数据对比——带您随时观测数据一致性
- “==”和“===”,难道不是多一个的区别吗?
- 详解图像处理的算术运算与逻辑运算
- 设计秒杀系统架构,这4个关键点要注意