- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
作者: Grey 。
原文地址:
博客园:寻找链表相交结点问题 。
CSDN:寻找链表相交结点问题 。
给定两个可能有环也可能无环的单链表,头节点head1和head2。请实现一个函数,如果两个链表相交,请返回相交的 第一个节点。如果不相交,返回 null.
要求:如果两个链表长度之和为N,时间复杂度请达到 O(N) ,额外空间复杂度请达到 O(1) .
见: 寻找链表的入环节点和相交节点问题 .
本题主要的难点是要分析所有可能的情况,因为题目中提到「可能有环也可能无环」.
先看大的情况,有如下三种情况 。
第一种情况:两个链表均无环; 。
第二种情况:两个链表均有环; 。
第三种情况:一个有环,一个无环.
首先,第三种情况下,两个链表一定不相交。针对第一种情况,就是 寻找链表的入环节点和相交节点问题 中提到 LeetCode 160. Intersection of Two Linked Lists ,现在只分析第二种情况.
由于两个链表都有环,两个链表如果相交,一定只有如下三种情况 。
情况1:两个链表独立不相交 。
情况2:两个链表的入环结点是同一个 。
情况3:两个链表的入环结点不是同一个,此时任意一个链表的入环结点都是相交结点.
先从最简单的情况1和情况3进行分析,情况一发生的条件是:两个链表的入环结点(loop1,loop2)不是同一个,判断条件很简单,就是从任意一个链表的入环结点开始遍历一圈,如果都没有遇到另外一个链表的入环结点, 两个链表不相交,属于情况1; 。
如果从任意一个链表的入环结点开始遍历一圈,遇到了另外一个链表的入环结点,则说明两个链表相交,属于情况3,且任意一个链表的入环结点都是相交结点.
最后分析情况2,两个链表的入环结点如果是同一个,可以记录两个链表的差值,然后让短链表先走差值步以后,长短链表同时开始走,相遇的结点就是第一个相交结点.
完整代码见:
public class Code_FindFirstIntersectNode {
public static class List {
public int val;
public List next;
public List(int v) {
val = v;
}
}
public static List getIntersectNode(List head1, List head2) {
if (head1 == null || head2 == null) {
return null;
}
// 两个均无环
List loop1 = getLoopNode(head1);
List loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
// 两个均有环
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
// 一个有环一个无环 ,不可能相交
return null;
}
// 找到链表第一个入环节点,如果无环,返回null
public static List getLoopNode(List head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// 慢指针 在第一个节点位置
List slow = head.next;
// 快指针,在第二个节点的位置
List fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
// 快指针每次走两步
fast = fast.next.next;
// 慢指针每次走一步
slow = slow.next;
}
// 两个指针遇上了,说明有环
// 让快指针回到头部, 慢指针停在原地
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 快指针每次走一步,慢指针每次走一步,遇上后,就是入环节点处
return slow;
}
// 如果两个链表都无环,返回第一个相交节点,如果不想交,返回null
public static List noLoop(List head1, List head2) {
if (head1 == null || head1 == null) {
return null;
}
// 判断两个链表的长度
int n = 0;
List t1 = head1;
List t2 = head2;
while (t1.next != null) {
n++;
t1 = t1.next;
}
while (t2.next != null) {
n--;
t2 = t2.next;
}
// 两个链表的末节点不相等
if (t2 != t1) {
return null;
}
// 记录长的链表头节点
List longer = n > 0 ? head1 : head2;
// 记录短的链表头节点
List shorter = longer == head1 ? head2 : head1;
// 先让长链表走一段距离(这段的长度就是长链表和短链表的长度差)
int gap = Math.abs(n);
while (gap != 0) {
gap--;
longer = longer.next;
}
// 然后长链表和短链表同时开始走,直到相等的节点即为交点
while (longer != shorter) {
longer = longer.next;
shorter = shorter.next;
}
return shorter;
}
// 两个有环链表,返回第一个相交节点,如果不想交返回null
public static List bothLoop(List head1, List loop1, List head2, List loop2) {
// 只有两种情况
if (loop1 == loop2) {
// 1. 未入环就相交
// 这种情况下,两个链表的入环节点是一样
int n = 0;
List t1 = head1;
List t2 = head2;
while (t1 != loop1) {
n++;
t1 = t1.next;
}
while (t2 != loop2) {
n--;
t2 = t2.next;
}
List longer = n > 0 ? head1 : head2;
List shorter = longer == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
longer = longer.next;
}
while (longer != shorter) {
longer = longer.next;
shorter = shorter.next;
}
return shorter;
} else {
// 2. 共用环,不在入环处相交,随便一个链表的入环点就是交点
// loop1 != loop2
// 从loop1开始,转一圈回到loop1
// 如果都没有遇到loop2,则不相交
// 如果遇到了loop1,则交点为loop1或者loop2都可以
List t1 = loop1.next;
while (t1 != loop1) {
if (t1 == loop2) {
return loop1;
}
t1 = t1.next;
}
return null;
}
}
}
算法和数据结构笔记 。
最后此篇关于寻找链表相交结点问题的文章就讲到这里了,如果你想了解更多关于寻找链表相交结点问题的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
题: 是否有一种简单的方法可以获取正在运行的应用程序中泄漏的资源类型列表? IOW 通过连接到应用程序? 我知道 memproof 可以做到,但它会减慢速度,以至于应用程序甚至无法持续一分钟。大多数任
正确地说下面的代码会将自定义日志发送到.net核心中的Docker容器的stdout和stderr吗? console.Writeline(...) console.error(..) 最佳答案 如果
我想将一个任务多次重复,放入 for 循环中。我必须将时间序列对象存储为 IExchangeItem , openDA 中的一个特殊类(数据同化软件)。 这是任务之一(有效): HashMap ite
我需要从文件中读取一个数组。该数组在文件中不是连续排序的,必须跳转“偏移”字节才能获得下一个元素。假设我读取一个非常大的文件,什么更有效率。 1) 使用增量相对位置。 2)使用绝对位置。 选项 1:
我有一个安装程序(使用 Advanced Installer 制作)。我有一个必须与之交互的应用程序,但我不知道如何找到该安装的 MSIHANDLE。我查看了 Microsoft 引用资料,但没有发现
我在替换正则表达式中的“joe.”等内容时遇到问题。这是代码 var objects = new Array("joe","sam"); code = "joe.id was here so was
我有 A 类。A 类负责管理 B 对象的生命周期,它包含 B 对象的容器,即 map。 ,每个 B 对象都包含 C 对象的容器,即 map .我有一个全局 A 对象用于整个应用程序。 我有以下问题:我
任何人都可以告诉我在哪里可以找到 freeImage.so 吗?我一直在努力寻找相同的东西但没有成功..任何帮助将不胜感激。我已经尝试将 freeimage.a 转换为 freeImage .so 并
在单元测试期间,我想将生成的 URL 与测试中定义的静态 URL 进行比较。对于此比较,最好有一个 TestCase.assertURLEqual 或类似的,它可以让您比较两个字符串格式的 URL,如
'find ./ -name *.jpg' 我正在尝试优化上述语句的“查找”命令。 在查找实现中处理“-name”谓词的方法。 static boolean pred__name __common (
请原谅我在这里的困惑,但我已经阅读了关于 python 中的 seek() 函数的文档(在不得不使用它之后),虽然它帮助了我,但我仍然对它的实际含义有点困惑,任何非常感谢您的解释,谢谢。 最佳答案 关
我在我正在使用的库中找到了这个语句。它应该检查集群中的当前节点是否是领导者。这是语句:(!(cluster.Leader?.IsRemote ?? true)) 为什么不直接使用 (cluster.L
我发现 JsonParser 在 javax.json.stream 中,但我不知道在哪里可以找到它。谁能帮帮我? https://docs.oracle.com/javaee/7/api/javax
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗?更新问题,使其仅关注一个问题 editing this post . 6年前关闭。 Improve this questi
如果 git 存储库中有新的更改可用,我有一个多分支管道作业设置为每分钟由 Jenkinsfile 构建。如果分支名称是某种格式,我有一个将工件部署到环境的步骤。我希望能够在每个分支的基础上配置环境,
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗?更新问题,使其成为 on-topic对于堆栈溢出。 6年前关闭。 Improve thi
我想我刚刚意识到当他们不让我使用 cfdump 时我的网络主机是多么的限制。这其实有点让我生气,真的,dump 有什么害处?无论如何,我的问题是是否有人编写了一个 cfdump 替代方案来剔除复杂类型
任务:我有多个资源需要在一个 HTTP 调用中更新。 要更新的资源类型、字段和值对于所有资源都是相同的。 示例:通过 ID 设置了一组汽车,需要将所有汽车的“状态”更新为“已售出”。 经典 RESTF
场景:表中有 2 列,数据如下例所示。对于“a”列的相同值,该表可能有多个行。 在示例中,考虑到“a”列,“1”有三行,“2”有一行。 示例表“t1”: |a|b ||1|1.1||1|1.2||1
我有一个数据框: Date Price 2021-01-01 29344.67 2021-01-02 32072.08 2021-01-03 33048.03 2021-01-04 32084.
我是一名优秀的程序员,十分优秀!