链表在面试和笔试中都是十分常见的问题。本篇文章会简述到判断环形链表和返回环形链表的入环点。其中有较多的细节，本篇文章会详细解释。
一、判断环形链表
1、1 题目描述
题目来源：Leetcode
题目难度：简单
题目描述：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
1、2 题解详细思路与解答
我们发现，环形链表是不能够随对其进行遍历的，如果不加任何操作，会很容易造成死循环。那怎么判断是否有环呢？我们不妨用一下追赶问题去考虑一下。也就是快慢指针。如果有环的话，快指针会先走进环内，并且一直在环内进行循环。慢指针会后进入环内。当两个指针都进入环内时，就成为了一个追击问题了。我们不妨设置快指针一次走两个节点，慢指针一次走一个节点，两个指针都进入环内就成为了快指针追击慢指针的情况了。此时如果有环一定会相遇。
我们先看代码的实现：
bool hasCycle(struct ListNode *head) { if(head==NULL) return false; struct ListNode *slow=head,*fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; }
上述代码中，如果没有环，当链表中节点个数为奇数时，fast->next 为空时是截至条件。当链表的节点个数为偶数时，fast 为空时是截至条件。
二、找环形链表的入环点
2、1 题目描述
题目来源：Leetcode
题目难度：中等
题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。
2、2 题解思路
当我们在做判断环形链表时，我们设置的快指针一次走两个节点，慢指针一次走一个节点。为什么要这样设置呢？那么快指针一次走三步、四步……呢？这其中到底与什么有关呢？我们继续往下分析。
2、2、1 为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚
进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
我们发现上述重点是在分析的相对速度。即我们可以看成慢指针没有走，快指针每次走一步在追赶，不会错过的，一定会追上并且相遇的。
2、2、2 快指针一次走3步，走4步，...n步行吗？
为什么slow走1步，fast走x步(X>=3)，他们会相遇?会不会错过?请证明。我们先来看快指针一次走3步，慢指针一次走1步的情况。
假设slow进环的时候fast和slow之间距离是N。slow进环以后，fast开始追击slow，slow每走1步，fast走3步，他们之间的距离缩小2。假设fast和slow之间的距离为偶数，那么每次距离缩减2，那么一定会追上且会相遇。假设fast和slow之间的距离为奇数，第一圈fast会超过slow，会追上但不会相遇。那么第二圈的时候，它们之间的距离变成了N-1。距离就变成了偶数了，第二圈会追上且相遇。
那么快指针一次走4步，慢指针一次走1步的情况呢？我们再来分析一波。
假设slow进环的时候fast和slow之间距离是N。slow进环以后，fast开始追击slow，slow每走1步，fast走4步，他们之间的距离缩小3。假设N是3的倍数，那么每次距离缩小3，第一圈就会追上并且相遇。那么如果N不是3的倍数，是N%3为2，第一圈并不会相遇，第二圈距离会变成N-1。(N-1)%3为1，第二圈又不会相遇。第三圈距离会变成N-1-2，我们发下减去3相当于没减。会一直循环下去，并不会相遇。当N%3为1时，与上述中的一种情况一样，也会陷入死循环。所以快指针一次走4步，慢指针一次走1步的情况是不行的。
2、2、3 是否能够相遇关键因素
通过上面的两种情况的分析，发现快慢指针能否相遇，关键是有两个因素：慢指针进环时与快指针之间的距离和两者的相对速度。那怎么找入环点呢？
2、3 找入环点
我们接着分析：
我们在这里不妨分析一下快慢指针的整个过程，如下图：
我们就以快指针每次走两步，慢指针走一步的情况进行分析。那么当两个指针相遇时，slow一定时走的环形的第一圈。因为我们假如slow在环内走了一圈多，那么fast最少走了两圈，因为相对速度为1，追上即相遇，当fast走到两圈多的情况下早就相遇过，故slow走一圈多不成立。但是在slow入环之前，fast已经在环内走了很多圈（我们假设已经走了n圈，n可能等于1，2……）。故相遇时我们可以列出两者的距离等式：2*（L+X）=L+n*C+X。我们在对等式进行变换：L=n*C-X。我们在对等式进行分析：L为入环前的距离，n*C-X=（n-1）*C + C-X。这里我们这能算出C环的长度，其他的都是未知数。这个L=（n-1）*C + C-X等式也就意味着，在有环的情况下，一个指针从起始点走，一个指针从相遇点走，从相遇点走的指针可能在环内走了很多圈，也有可能一圈也没有，那么两个点再次相遇的位置即为入环点的位置了。我们再看代码：
struct ListNode *detectCycle(struct ListNode *head) { if(head==NULL) return NULL; struct ListNode* fast=head,*slow=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) { struct ListNode* meet=fast; struct ListNode* phead=head; while(phead!=meet) { phead=phead->next; meet=meet->next; } return meet; } } return NULL; }
三、总结
上述的问题在面试中很常见，问怎么看是否有环，为什么快指针每次走两步，慢指针走一步可以？快指针一次走3步，走4步，...n步行吗？还有一个就是找入环点的位置。希望本编文章会对你有所帮助，可以很好的解决这些问题。一定要搞清楚细节问题，不要只记结论，否则会吃大亏。
本篇文章的讲解就到这里，希望以上内容会对你有所帮助，感谢观看ovo~
