共计 1818 个字符，预计需要花费 5 分钟才能阅读完成。
首先，关于单链表中的环，一般涉及到以下问题：
1. 给一个单链表，判断其中是否有环的存在；
2. 如果存在环，找出环的入口点；
3. 如果存在环，求出环上节点的个数；
4. 如果存在环，求出链表的长度；
5. 如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.（扩展）如何判断两个无环链表是否相交；
7.（扩展）如果相交，求出第一个相交的节点；
下面，我将针对上面这七个问题一一给出解释和相应的代码。
1. 判断时候有环（链表头指针为 head）
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针 fast 和 slow，开始的时候两个指针都指向链表头 head，然后在每一步
操作中 slow 向前走一步即：slow = slow->next，而 fast 每一步向前两步即：fast = fast->next->next。
由于 fast 要比 slow 移动的快，如果有环，fast 一定会先进入环，而 slow 后进入环。当两个指针都进入环之后，经过一定步的操作之后
二者一定能够在环上相遇，并且此时 slow 还没有绕环一圈，也就是说一定是在 slow 走完第一圈之前相遇。证明可以看下图：
当 slow 刚进入环时每个指针可能处于上面的情况，接下来 slow 和 fast 分别向前走即：
if (slow != NULL && fast->next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
} 也就是说，slow 每次向前走一步，fast 向前追了两步，因此每一步操作后 fast 到 slow 的距离缩短了 1 步，这样继续下去就会使得
两者之间的距离逐渐缩小：…、5、4、3、2、1、0 -> 相遇。又因为在同一个环中 fast 和 slow 之间的距离不会大于换的长度，因此
到二者相遇的时候 slow 一定还没有走完一周（或者正好走完以后，这种情况出现在开始的时候 fast 和 slow 都在环的入口处）。
问题 1 是否存在环的解答
typedef struct node{
char data ;
node * next ;
}Node;
bool exitLoop(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
return true ;
}
return false ;
}问题 2 环的入口点：
从上面的分析知道，当 fast 和 slow 相遇时，slow 还没有走完链表，假设 fast 已经在环内循环了 n(1<= n)圈。假设 slow 走了 s 步，则 fast 走了 2s 步，又由于
fast 走过的步数 = s + n*r（s + 在环上多走的 n 圈），则有下面的等式：
2s = s + n r；（1）
=> s = n*r；（2）
如果假设整个链表的长度是 L，入口和相遇点的距离是 x（如上图所示），起点到入口点的距离是 a(如上图所示)，则有：
a + x = s = n * r; (3) 由（2）推出
a + x = (n – 1) r + r = (n – 1) r + (L – a) (4) 由环的长度 = 链表总长度 – 起点到入口点的距离求出
a = (n – 1) * r + (L -a -x) (5)
从式子（5）以及上图我们可以看出，从链表起点 head 开始到入口点的距离 a, 与从 slow 和 fast 的相遇点（如图）到入口点的距离相等。
因此我们就可以分别用一个指针（ptr1, prt2），同时从 head 与 slow 和 fast 的相遇点出发，每一次操作走一步，直到 ptr1 == ptr2，此时的位置也就是入口点！
到此第二个问题也已经解决。
Node* findLoopStart(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast) break ;
}
if (slow == NULL || fast -> next == NULL) return NULL ; // 没有环，返回 NULL 值
Node * ptr1 = head ; // 链表开始点
Node * ptr2 = slow ; // 相遇点
while (ptr1 != ptr2)
{
ptr1 = ptr1 -> next ;
ptr2 = ptr2 -> next ;
}
return ptr1 ; // 找到入口点转载原文：https://blog.csdn.net/doufei_…
