当我们做链表的编程题时，经常会遇到给定一个单链表（头结点）判断单链表知否带环等如下的问题。 1. 判断链表是否带环？ 2. 环的入口位置在哪里？ 3. 环的长度是多少。
问题1： 首先要判断一个链表是否带环，我们可以分别考虑一下带环和不带环两种情况的区别。如果链表不带环，我们用一个指针从头遍历到尾 指针最终会指向一个NULL 。如果链表带环指针一旦进入环就会一直循环遍历，这样就会陷入死循环永远走不到 NULL位置。 这时我们可以考虑用两个指针去遍历整个链表，分别为fast和slow，fast一次走两步，slow一次走一步，如果链表不带换那么fast或者 fast->next就会走到 NULL，如果链表带环，fast和slow就会在环的某一个节点相遇，这样我们就能很快判断出链表是否带环了。
代码如下（判断链表是否带环）：
ListNode* IsExitsLoop(ListNode* pHead) { if(pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) return NULL; ListNode* slow = pHead->next,*fast = pHead->next->next; while(slow!=fast) { if(fast == NULL || fast->next == NULL) { cout<<"不带环"<<endl; return NULL; } slow = slow->next; fast = fast->next->next; } cout<<"带环"<<endl; return slow; }问题2： 如果该链表已经证明带环，那么环的入口地址在哪里？我们用下图来详细说明一下。上一步我们通过slow和fast相遇得出链表带环，如图所示 假设相遇在M点，设环的入口位置为点P，链表头结点为B，从B到P我们假设长度为L，从P到M长度记为S，整个环长度为C。我们分析一下fast和slow从出发到相遇一共走了多长？ 对于fast：因为相遇之前可能在环内循环了n圈所以总路程为 L+nC+S 对于slow：总路程为 L+S 由于slow每次走一步，fast每次走两步。因此就有了 L+nC+S = 2（L+S） 解方程得到：L = nC - S 。这个等式什么意义？M点现在是fast和slow相遇的位置 我们可以记录这个位置，让一个cur从链表头B出发每次走一步，slow指针继续从相遇的点出发每次一步，当cur走了L长后到了环入口P，此时slow指针到哪里呢？ 我们分析一下，slow之前已经从P点走了S长，从解方程的结果可以得出S = nC-L ， 此时给slow再走L长即 S+L 就神奇的到了环的入口。 所以当cur和slow相遇的地方就是环的入口。 //带环链表图示
代码如下（环的入口地址）：
ListNode* FindLoopPort(ListNode* pHead) { if(pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) return NULL; ListNode* slow = pHead->next,*fast = pHead->next->next; while(slow!=fast) { if(fast == NULL || fast->next == NULL) return NULL; slow = slow->next; fast = fast->next->next; } slow = pHead; while(slow != fast) { slow = slow->next; fast = fast->next; } return slow; }问题3： 已经知道了环的入口位置，我们让一个指针从环入口出发，当再次走到该位置时走过的长度就是环的长度了。 代码如下（环的长度）：
int LoopPortLength(ListNode* pPort) { ListNode* pCur = pPort->next; int length = 1; while(pCur != pPort) { pCur = pCur->next; length++; } return length; }