【LeetCode刷题日记】142.环形链表Ⅱ

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言今天是链表篇章的最后一题但是对于新手来说一看题目就有点胆怯了这题可以说是纸老虎了虽然看着不是很简单其实也不是那么简单里面需要注意很多细节地方还有一些简单的推理所以还是需要重点理解的。题目背景LeetCode142给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引题目答案public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) {// 有环 ListNode index1 fast; ListNode index2 head; // 两个指针从头结点和相遇结点各走一步直到相遇相遇点即为环入口 while (index1 ! index2) { index1 index1.next; index2 index2.next; } return index1; } } return null; } }题目解析这题代码看着很简单很少但是重点是思路下面我们具体分析首先我们第一个需要判断的就是链表是否有环。这里我们使用快慢指针的方式分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。为什么fast 走两个节点slow走一个节点有环的话一定会在环内相遇呢而不是永远的错开呢这就需要好好解释一下了首先既然是快指针肯定是先进入环中的因为fast指针每次移动两个节点为什么是两个节点后面我们就知道了fast进入环中之后那肯定就一直在环中运动与慢指针也只能是在环中相遇我们可以用相对运动的方式此时相对于慢指针快指针始终以每次一个节点的速度靠近慢指针此时慢指针相对静止。那么只要是有环快指针就一定能追上慢指针。我们也可以画图模拟一下过程随机让fast指针在任意一个节点开始追慢指针发现最后都是快指针差一个节点追上慢指针。动态过程如图解决了第一个问题之后那么继续回到题目的要求要求返回链表开始入环的第一个节点若链表无环则返回null这个已经在第一步解决了。假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示那么相遇时slow指针走过的节点数为:x y fast指针走过的节点数x y n (y z)n为fast指针在环内走了n圈才遇到slow指针 yz为 一圈内节点的个数A。因为fast指针是一步走两个节点slow指针一步走一个节点 所以fast指针走过的节点数 slow指针走过的节点数 * 2(x y) * 2 x y n (y z)两边消掉一个xy:x y n (y z)因为要找环形的入口那么要求的是x因为x表示 头结点到 环形入口节点的的距离。所以要求x 将x单独放在左面x n (y z) - y,再从n(yz)中提出一个 yz来整理公式之后为如下公式x (n - 1) (y z) z这里我们也可以使用从特殊到一般的办法递归寻找对n进行赋值也能发现这一规律。注意这里n一定是大于等于1的因为 fast指针至少要多走一圈才能相遇slow指针。由此我们就可以找到入环的第一个节点。如下操作if (slow fast) {// 有环 ListNode index1 fast; ListNode index2 head; // 两个指针从头结点和相遇结点各走一步直到相遇相遇点即为环入口 while (index1 ! index2) { index1 index1.next; index2 index2.next; } return index1; }同时这里又有一个问题了为什么n一定是大于等于一呢就好比跑步一样一个快的追一个慢的那么你们要想相遇就一定是快的跑了一圈之后或者n之后追到了慢的毕竟不可能反向跑吧。易错点为什么第一次在环中相遇slow的 步数 是 xy 而不是 x 若干环的长度 y呢需要注意的是我们要讨论的是第一次相遇的时候这时就一定有slow 刚进入环的那一刻环长 L y z1. slow 刚入环时位置在哪里slow 在环入口fast 已经在环里面某个位置2. 两者之间的距离因为 fast 速度是 2 倍slow 走 x 时fast 走 2x。所以 fast 已经领先一段距离。但不管领先多少距离一定满足0 ≤ 距离 d L不可能 ≥ L否则 fast 早就多跑一圈了。两者距离取模后一定0 ≤ d L相对速度 1所以d 步必相遇d L →slow 不可能走满一圈fast 也不需要跑一圈就能追上3. 接下来开始追slow 速度1fast 速度2每走 1 步fast 靠近 slow1 步距离是 d所以只需要d 步就会相遇。4. 关键来了因为d L所以 slow 在环里只走了d 步就相遇了。也就是说slow 在环里走的步数 y d Ly 环长→ slow根本没走完一圈就被追上了。第一次相遇时慢指针一定没有走完一圈环所以它的路程只能是 xy不可能带上若干个环。数学推理slow 进环前走的距离x环的总长度nslow 进环时fast 距离环入口的长度k且k n因为在环里1. 第一句重点slow 进环的时候fast 一定已经在环里了。→ 这个没问题因为 fast 快。2.核心推理重点当 slow刚进环时fast 已经在环里某个位置fast 距离环入口的长度是kk 一定小于 n3. 原文最关键一句fast 走到环入口时走了 k n 步那么 slow 应该走了 (k n)/2 步因为 fast 速度是 2 倍路程也是 2 倍。4. 最关键不等式决定一切因为k n所以(k n) / 2 (n n) / 2 n也就是说slow 走的距离 nn 是一环的长度。5. 最终结论slow 还没走完一环fast 已经回到环入口了这意味着在 slow 走完第一环之前fast 必然追上 slow6. 所以第一次相遇时slow 绝对不可能走完一环slow 走过的路程一定是 x y绝对不可能是 x 一环 y结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励