力扣每日一题（环形链表II）

深碍√TFBOYSˉ_ 2024-04-23 15:37 81阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[一起刷好题][Link 2]
> 
> ?每日一句**：人总是珍惜未得到的，而遗忘了所拥有的。**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

**题目如下：**

![6b80c04da64646e4b2a83ca4e422d5ac.png][]

> **原题链接： [环形链表II——力扣][II]**

> **分析：对于这个题目我们首先要判断这个链表是不是有环，然后再去找到环的入口**

**?我们上文提到：如果定义两个对结点的引用变量fast和slow，他们一开始都分别指向头结点。但不同的是fast每次移动两个结点，slow每次移动一个结点。他们如果相遇就说明这个链表一定有环**

![df8f2aeba032770d580827ae7529c7b8.gif][]

**然后如果有环的话， 就要找到环的入口结点。**

我们知道当fast和slow所对应的结点相遇时，**fast一定是比slow要多走了几个环的长度的（也正是这几个环的长度抵消了fast比slow每一步所多走的结点数**）

那么现在对整个链表来说，有这么几个点是需要我们关注的：**环的入口结点、fast和slow的相遇结点**。那么我们就可以画出这样的图：

![76c357a33a55d9d072a47d8eb4288cd5.png][]

> ?**那么当fast和slow相遇时 ：slow走了：x+y个结点，fast走了：x+y+n(y+z)个结点，其中y+z是环的长度，此时相当于fast比slow多走了n个环的长度（n>=1，n至少为1，要不然快慢指针也不可能相遇)。**
> 
> **我们知道fast一次走两个结点、slow一次走一个结点，同时fast和slow走的次数是相同的，所以说fast走的结点数就是slow走的结点数的两倍**

即：**n(y+z) == x + y，**我们要求的是**x的长度（环的入口结点），**那么上式就可以写成

> **x = (n-1)(y+z) + z（n >= 1）**

?当n等于1时，即x==z，从图上我们可以想象一下如果此时**一个结点index1从相遇结点开始走，另一个结点index2从头结点开始走，**每次他们两个走相同的结点数，那么他们不就会在环的入口结点相遇吗？

?当n大于1时候，即**x = z + 几个环的长度 ，**此时无非就是相当于从相遇结点出发的index1绕着环多走了几圈，然后才和从头结点出发的index2相遇。**此时index2走了x个长度，index1走了z+几个环的长度。**

**? 代码如下：**

>     public class Solution {
>         public ListNode detectCycle(ListNode head) {
>             if (head == null || head.next == null) return null; // 如果在链表只有一个结点或者没有结点，一定为无环
>             ListNode fast = head, slow = head;
>             while (fast != null && fast.next != null) {
>                 slow = slow.next;
>                 fast = fast.next.next;
>                 if (slow == fast) break; // 快慢指针相遇：说明有环
>             }
>             if (fast == null) return null; // 如果是因为fast == null 退出循环的话，说明无环
>             else {
>                 // 一个结点index1从相遇结点开始走，另一个结点index2从头结点开始走
>                 ListNode index1 = slow, index2 = head;
>                 while (index1 != null && index2 != null) {
>                     if (index1 == index2) break; // if要放在前面，处理当入环的结点是0的这种情况
>                     index1 = index1.next;
>                     index2 = index2.next;
>                 }
>                 return index1; // 他们两个结点的相遇处，就是环的入口
>             }
>         }
>     }

**运行结果**

![31d2da9903b9479388270da2814d2a47.png][]

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Link 2]: https://blog.csdn.net/weixin_61061381/category_11776133.html
[6b80c04da64646e4b2a83ca4e422d5ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/37ead0d565774ea3b9e3176f02fe0552.png
[II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[df8f2aeba032770d580827ae7529c7b8.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5c445f54707b40acac8297b3b0a690a4.gif
[76c357a33a55d9d072a47d8eb4288cd5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4a68190d48574284bd749fa192baf1d1.png
[31d2da9903b9479388270da2814d2a47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a187b352edd441d280aede703ae73196.png