点首先，单链表中的环一般涉及以下问题：1.给一个单链表，判断是否有响起来；2.如果有环，找到环的入口点；3.如果有环，求环上的节点数；4.如果有环，求链表的长度；5.如果有环，找到环上距离任意节点（对端节点）最远的点；6.（扩展）如何判断两个无环链表是否相交；7.（扩展）如果它们相交，则找到点一个相交节点；下面，我将对以上七个问题一一给出解释和相应的代码。1.判断的时候有循环（链表头指针为head）。这个问题我们可以用“快慢指针”的方法。即有快慢两个指针。一开始，两个指针都指向链表的头部，然后在每一步操作中，slow向前走一步：slow=slow->next，fast每走一步向前走两步。:fast=快速->下一步->下一步。由于快的比慢的快，如果有环的话，快的肯定先进环，慢的后进环。当两个指针都进入圆环时，它们必须经过一定的运算步骤才能在圆环上相遇，而此时slow还没有绕完圆环，也就是说它们必须在slow完成第一圈之前相遇。证明见下图：当slow先入环时，每个指针都可能出现上述情况，然后slow和fast分别向前移动：if(slow!=NULL&&fast->next!=NULL){慢=慢->下一步;fast=fast->next->next;}也就是说每slow向前走一步，fast追前两步，所以每次操作后fast到slow的距离都会缩短一步，这样继续下去会让两者的距离逐渐缩小：。..,5,4,3,2,1,0->相遇。又因为在同一个环中快慢之间的距离不会大于变化的长度，所以慢在两者相遇的时候一定还没有完成一个星期（或者刚好在结束之后，这种情况出现在开始的时候快和慢都慢在环的入口处）。回答问题1是否存在循环typedefstructnode{chardata;下一个节点；}节点;boolexitLoop(Node*head){Node*fast,*slow;慢=快=头；while(slow!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;如果（慢==快）返回真；}返回假；分析发现，当fast和slow相遇时，slow还没有链表走完，假设fast已经在环中循环了n(1<=n)圈。假设slow走了s步，然后fast走了2s步，由于fast走的步数=s+n*r（s+环上还有n圈），那么就有下面的等式：2s=s+nr;(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)从环的长度=链表的总长度-起点到入口点的距离而从上图我们可以看出链表起点到头的距离alist到入口点等于slow和fast的交汇点（如图）到入口点的距离。因此，我们可以分别用一个指针（ptr1，prt2），同时从head、slow和fast的交汇点开始，每操作一步，直到ptr1==ptr2，此时的位置是切入点！至此第二个问题也解决了。Node*findLoopStart(Node*head){Node*fast,*slow;慢=快=头；while(slow!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;如果（慢==快）中断；}if(slow==NULL||fast->next==NULL)returnNULL;//没有循环，返回NULL值Node*ptr1=head;//链表起点Node*ptr2=slow;//集合点while(ptr1!=ptr2){ptr1=ptr1->next;ptr2=ptr2->下一个；}返回ptr1;//找到入口点第三题，如果有环，求环上的节点个数：方法一：记录遇到的节点，存入临时变量tempPtr，然后让slow（或者fast，两者都some)继续前进slow=slow->next;直到慢==tempPtr；此时经过的步数就是环上的节点数；方法二：从会合点出发，慢快继续原路前行slow=slow->next；fast=fast->next->next;直到两人再次进入，此时经过的步数就是环上的节点数。两种方法的本质是一样的，他们在会合点重新开始行走，直到再次相遇。问题4是如果有环，求链表的长度：问题2已经知道起点到入口点的距离，问题3知道环的长度r；链表长度L=起点到入口点的距离+环的长度r；第5题如下图所示，求出环上离任一节点（对端节点）最远的点。1点和4点，2点和5点，3点和6点互为“对立节点”，也就是把最远的点放在最上面，我们的需求是如何找到任意一点上的最远点。为了替换任何点ptr0，我们需要找到它的“对立点”。我们可以这样想：用上面fast和slow指针一样的方法，让slow和fast指向ptr0，每一步都进行和上面一样的操作（slow每次跳一步，fast每次跳两步time),当fast=ptr0或fast=prt0->next时，slow指向的节点是ptr0的“对端节点”。如上图，我们假设环是从ptro展开的，展开后可以无限长（同上，6之后重复前面的内容）如上图。现在问题就简单了，因为slow和fast的移动距离总是一样的，所以当fast遍历整个环长的r个节点时，slow刚好遍历r/2个节点，也就是说刚好指向距离ptr0的最远点。转载原文：https://blog.csdn.net/doufei_...
