茕茕白兔，东走西顾，衣不如新，人不如故
往期回顾：
数据结构——双向链表
数据结构——单链表
数据结构——顺序表
文章目录
如何判断一个链表是否为环形链表
环形链表的判断的深入探究
例1：沸羊羊追美羊羊
例2：灰太狼追懒羊羊
判断方法结论总结
环形链表的入口结点
源码及思路
另辟蹊径
大家好，我是纪宁。这篇文章将深入探究环形链表。
环形链表的形成是因为当单链表最后一个结点的指针域没有指向空，而指向了前面的任意一个结点。单链表链表一旦成环，在遍历的时候就会造成在一个区域里循环，那么对于环形链表的探究也应运而生。
在现实情况中，链表不可能这么短，所以如何判断链表是否成环，链表在何处成环，就成为了我们学习链表之后必须要研究的问题，也成为了面试题和笔试题中最喜欢考察的部分。
在上一篇链表刷题总结快慢指针的时候，博主曾粗略的谈到了环形链表的概念。这篇文章，博主带大家深入探究并总结，也算是博主自我内核的进一步提升吧。上篇文章的链接：快慢指针
如何判断一个链表是否为环形链表
首先，要明白环形链表的特征，如果定义一个指针去维护环形链表，它会在特定的位置进入环形链表内部，然后一直在环形链表内部循环遍历，这里如果使用快慢指针的话，在思路上是比较好理解的：当一个快指针和一个慢指针一起从头结点往后走，如果链表存在环，那么快指针首先进入环中，而慢指针则后入环，快指针在一直绕环循环的时候，一定能追上慢指针。如果没有追上的话，说明快指针一直向后走，直到 NULL，则说明这个链表不是环形指针。
代码如下
bool hasCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
return true;
}
return false;
}
此代码将快指针定义为 fast ，慢指针定义为 slow，快指针每次向连链表末走两格，慢指针每次向链表末走一格（这里的走几格意思就是指针指向当前结点的后第几个结点），当两个指针相遇的时候，就说明这个链表带环。
环形链表的判断的深入探究
上段文章提到，快指针每次走两格，慢指针每次走一格，这里我们不禁有一些思考：真的能恰好追上吗？不会正好错过了吗？当快指针每次走三格，慢指针每次走一格呢？分析下面这几个例子。
例1：沸羊羊追美羊羊
沸羊羊跑的比较快，那么在无止尽的环中，它和美羊羊真的能正好相遇吗？
假设当美羊羊进入环中的时候，早已进入环中的沸羊羊和美羊羊在圆周上的距离为 N，而沸羊羊一次走的距离为 2，美羊羊一次走的距离为 1，沸羊羊每次比美羊羊多走的距离为 1 。
走 1 次后，他们俩之间的距离为 N-1
走 2 次后，他们俩之间的距离为 N-2
......
走 N-2 次后，他们俩之间的距离为 2
走 N-1 次后，他们俩之间的距离为 1
走 N 次后，他们俩之间的距离就为0，沸羊羊成功完美追上了美羊羊。
即使追上了，美羊羊就会接受沸羊羊吗？（开个玩笑）
这个例子说明了，快指针每次走两格，慢指针每次每次走一格，确实能相遇，可以用来判断环形链表，那么如果快指针每次走三格呢？
例2：灰太狼追懒羊羊
众所周知，红太狼爱吃羊，却从来没吃到过，但她有一个最疼爱她的老公灰太狼。灰太狼每天日复一日的想要抓到羊讨老婆换新，其中他最爱抓的羊，也是他觉得最好抓的羊，就是懒洋洋。
灰太狼和懒洋洋同时出发，灰太狼每次走三格，懒洋洋每次走一格，他们能完美相遇吗？
当懒洋洋进入环中时，灰太狼和它的举例为 M，环的长度为C，而懒洋洋每次走的距离为 1，灰太狼每次走的距离为 3，灰太狼比懒洋洋每次多走2灰太狼能否和懒洋洋完美相遇并抓到懒洋洋呢？
这种情况就和上面沸羊羊追美羊羊不一样了，无论沸羊羊和美羊羊距离多远，每次距离缩小1，总有一天距离会变为0。但灰太狼每次和懒洋洋的距离缩小 2，是否还会出现一直完美错过的情况。
假设灰太狼和懒洋洋之间的距离 M 为偶数，那么之间每次的距离为
M-2
M-4
......
2
0
这种情况是一定能追上的。
那么如果他们之间的距离 M 为奇数，那么他们之间每次的距离为
M-2
M-2
......
3
1
-1
当距离为-1时，灰太狼跑到了懒洋洋前面，那么灰太狼就刚好错过了懒洋洋，要进行下一圈追击。并且追击的距离与环的周长C有关，因为这次要追击的距离为 C-1。
当 C-1 为偶数，即周长C为偶数时，则恰好可以追上懒洋洋，如果C-1 依然为奇数，即周长C为偶数时，那这次也追不上懒洋洋了。因为这次追击的距离为奇数，所以下次追击的距离依然为 C-1 为奇数，这就成了一个死循环，这种情况下灰太狼就永远也抓不到懒洋洋！
判断方法结论总结
当快指针每次走两步，慢指针每次走一步的时候，这两个指针一定能相遇，这种方法可以判断出链表是否为环形链表。
当快指针每次走三步，慢指针每次走一步的时候，这两个指针是否相遇得取决于进入环中时两指针的距离，当这个距离为偶数时，则一定能相遇；当这个距离为奇数时，还要看环的周长，如果环的周长为奇数时，则可以相遇，当环的长度为偶数时，则永远不能相遇。这种方法不一定能判断出链表是否为环形链表。
当快指针每次走四步时，会有更复杂的情况......
环形链表的入口结点
当我们判断出了一个链表是否为环形链表的时候，还会思考，那这个链表是在哪个结点开始进入环的呢？
从上面那个例子中可以得出，快指针每次走两格，慢指针每次走一格，快指针一定能追上慢指针，可以判断出链表是否带环。
继续说美羊羊和沸羊羊那个例子，从上面的例子可以得之，当美羊羊进入环中时，沸羊羊一定能在一圈之内追上美羊羊。
设环的周长为4，环前面的链表长度为 L ，沸羊羊和美羊羊的相遇点与入环点的距离为 X，因为沸羊羊在美羊羊入环前可能已经绕环好几圈了，就设沸羊羊在和美羊羊相遇前已经在环里走了N 圈。
沸羊羊的速度是美羊羊的 2 倍，所以他们走的距离也是 2 倍关系
美羊羊走的距离为
沸羊羊走的距离为
列出等式为
得出 L 的值为
化简得
(N-1)*C 为沸羊羊在环里走的整圈的路程，而 (C-X) 为环的长度减去环的入口点到环的相遇点之间的长度。这个公式说明了一件事，当两个速度相同的指针，一个从起点开始走，一个从相遇点开始走，他们一定会在环入口点相遇（可能相遇前一个指针已经绕环很多圈了）。
源码及思路
首先，要找到快慢指针相遇的点，如果快慢指针没有相遇的话，则说明这个链表没有环。其次，重新定义两个速度相同的指针，一个从快慢指针的相遇点开始绕着环走，一个指针从起点开始走，这两个指针相遇的地方，就是环的入口结点。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head,*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)//相遇了
{
struct ListNode*cur1=head;
struct ListNode*cur2=fast;
while(cur1!=cur2)
{
cur1=cur1->next;
cur2=cur2->next;
}
return cur1;
}
}
return NULL;
}
这是力扣上一道中等难度的题，但是只要分析思路正确了，写代码就是分分钟的问题。
另辟蹊径
第一种思路，在很多人看来，特别是第一次接触这道题的人，比较难理解一点，那这里还有一种思路较为简单的方法，但简单的思路通常伴随着较为复杂的代码，可以说各有取舍吧，大家按需选择。
在此之前，博主在这里再介绍一个经典题目：
判断两个链表是否为相交链表，并找出他们的第一个共同结点
相交链表，即两个链表有重叠的公共结点，他们一旦有公共结点重叠，那么这个结点后面的结点就一定会重合。
判断环形链表的思路是，两个链表各定义一个指针来维护，先遍历计算出链表的长度，顺便比较链表最后一个结点是否重合，如果不重合，则肯定不是相交结点。先让较长链表的指针向前走 差值 步，然后两个指针同时走，直到有一个相同的结点，这个结点就是相交链表的第一个共同结点。
回到刚开始的问题，如何另辟蹊径找到环形链表的入口呢？既然刚才将了相交链表的思路，那肯定一想就直到：转化为相交链表求。
如图，在找到相遇点后，将相遇点断开。红色部分为一个链表，绿色部分为一个链表，他们组成一个相交链表，相交链表的第一个结点就是环形链表的入环结点。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenA=1,lenB=1;//求相交链表的第一个结点
struct ListNode*curA=headA,*curB=headB;
while(curA->next!=NULL)
{
curA=curA->next;
lenA++;
}
while(curB->next!=NULL)
{
curB=curB->next;
lenB++;
}
if(curA->val!=curB->val)
{
return NULL;
}
int dis=abs(lenA-lenB);//求差值绝对值
struct ListNode*longnode=headA,*shortnode=headB;
if(lenB>lenA)
{
longnode=headB;
shortnode=headA;
}
while(dis--)
{
longnode=longnode->next;
}
while(longnode!=NULL)
{
if(longnode==shortnode)
{
return longnode;
}
longnode=longnode->next;
shortnode=shortnode->next;
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)//求相遇点
{
struct ListNode *cur=fast->next;
fast->next=NULL;
return getIntersectionNode(cur,head);
}
}
return NULL;
}
这种方法虽然思路简单，但代码比较长，代码变长，就容易出错，所以说每种方法都是各有利弊。
