女朋友让我陪她在北京玩，于是我学会了怎么判断链表成环（超详解）数据结构与算法weixin44159662的博客-

第一次旅行

疫情期间在家憋了三个月，长胖了二十斤，我已然变成了个胖子，女朋友对我的身材管理很不满意，于是打着程序员容易猝死的旗号让我陪她出去旅行（逼我出去运动）。
那么怎么个运动法呢？骑车！地图如下：

女朋友小好要我去骑车，她说她坐顺风车监督我。为了能有效地督促我跑步，她让我先出发，一会打车追我。
于是我心（ji）甘（bu）情（qing）愿（yuan）地就出发了，

我终于抵达五棵松体育场，正当我准备去华熙live买冰激凌的时候，女朋友来电话对我说她要出发了，如果她追到我的时候还没抵达复兴门我就凉凉了。于是我立刻骑上了风火轮继续前行。

终于废了九牛二虎之力，我抵达了复兴门，好奇女朋友怎么还没追到我，结果得知她正在五棵松吃冰激凌？？心理极度不平衡的我决定在金融街打游戏，等她过来。
2000 years later…

终于，和女朋友在复兴门相遇了，由于顺风车不能停，她准备继续坐车在后面等我。
惊不惊喜、意不意外，女朋友就这样一直到了四惠。而我谎称到了天安门累了就骑回家休息去了。开心地吹着空调、盖着被子、吃着西瓜、看着电视、玩着手机。
后来，女朋友坐地铁到了家，指责我放她鸽子，我一脸无辜的样子让他无可奈何。

第二次旅行

第二天女朋友埋怨我昨天没怎么陪她，又提议出去玩。这次她定了新的路线，而且还是让我先行：
我依旧先到了五棵松，然后考虑到打车太贵，我提议让她坐公交。于是她答应了我依旧叫了顺风车- -。

一切都和昨天一样，她依旧买了冰激凌，和我相遇后依旧准备在后面等我。而我也准备故技重施，在复兴门休息。

结果往往没想到，我正想偷偷回家的时候女朋友竟然从南站大厦公园绕到了复兴门！
被女朋友一顿训斥后脑我又向前出发。结果开始了一圈又一圈的骑行…
不知道过了多久，最后在国贸相遇的时候我精疲力尽，表示再也不陪她玩了！

反思

我这两次的骑行路线，换成数据结构应该是这样：

以及

因为我先出发，而女朋友速度比我快，所以在第一天去无环图旅行的时候我们会相遇一次。而第二天局部有环时则会相遇无数次。
这么看来，判断有环无环就可以通过相遇次数解决，如果两个人速度不同（忽略变速运动），那么他们没相遇或者仅相遇一次证明是无环链表，如果大于一次则存在环路。

女朋友的嘲讽

“一个旅游路线有没有环还要这么复杂去判断？一眼不就看出来了？”

于是，我开始给她科普：

这个路线以链表存储在计算机是这样的，我们仅知道start的位置，以及后续的连接指向。如果想知道是否有环，需要从头到尾捋一遍线路，然后将已经捋过的地方做好标记记在本子上。每一次到达一个新地方都要去查小本本是否已经记录过了。然而这种模式效率过低，对系统内存消耗极大，所以在程序采用这种方法很不划算！

女朋友似（bu）懂（xiang）非（li）懂（wo）地点了点头。然后追问道“你说的意思我明白了，能把代码敲出来吗，我看（qu）看（wan）你（wang）咋（zhe）实（rong）现（yao）的（le）“。

实现过程

我们已知结论：速度不同的两个游标对链表做匀速遍历，如果相遇大于1次，则为有环链表。
我们不妨把情况改的简单一点，如果保证两个游标同时出发做速度不同的匀速运动，那么只要他们相遇了就证明链表有环。
为了方便理解，我们可以先想象成 慢的人速度为1、快的人速度为2。
开始写代码：

Node p1 = head;//先都指向头结点 Node p2 = head; int times = 0;//相遇0次 while(p2!=null&&p2.next!=null)//如果快游标到结尾就退出循环 {  p1=p1.next;//一次走一步  p2=p2.next.next；//一次走两步 if(p1==p2) { return isCycle;//相遇即证明有环 } } 

疑点解释

有没有可能在循环内慢速的游标会始终和快速游标无法相遇

如果你没有这个疑惑，就不用看了，如果你有，那么我跟你讲下为什么：
你的逻辑应该是这么想的：高速游标一直循环，低速游标也一直循环，但是由于高速游标步距为2，所以有可能导致慢游标始终无法相遇于在高速整点位置。
先放结论：不可能
公式推导（感谢评论区小伙伴）
前提：快慢游标进入循环后一定会先后落脚于同一个交点。
如下图所示，我们设圆为链表的循环部分，设其有8个循环结点。其中快游标的步距为2（速度为2），慢游标步距为1（速度为1）。故快游标的遍历路线为顺时针的绿色虚线，慢游标的遍历路线为顺时针橙色虚线。
不难看出快慢游标都会先后驻足于绿色点。

为了增加说服力，我们将慢游标步距设为2，快游标步距设为3， 还是存在不同时间的公共驻足点：

所以假设快慢游标先后落脚于循环结点x，如下图，此时快游标先抵达x，此时慢游标一定在它之前的某个结点：

然后慢游标抵达x结点，此时快游标可以在循环结点中的任何位置。

都进入循环链表后，我们希望会出现一下场景：快慢游标同时相遇于x结点。

已知：
慢游标步距分别为xA、xB；
链表中循环部分长度为s；
慢游标从进入循环结点x到两个游标相遇的时间为t；
推理：
(xA-xB)* t则为快游标在循环中比慢游标多走的距离。
只要满足：[(xA-xB)* t]%s=0即可证明它们会在循环中相遇于结点x。
故只要存在一个正整数t使得（xA-xB）*t = ns成立即可证明我们的假设。
因为xA！=xB，可得 t=ns/(xA-xB)不难看出（xA-xB）必为正整数，n为任意正整数，故一定存在一个正整数t使得等式成立。
结论：
综上所述，可得出，当快慢游标步距不相同的情况下，不论链表中循环结点的个数有多少，必定存在一个时刻t使得两个游标会在同一结点x相遇。