链表球环路的问题经常出现在面试题中，希望通过下面的解释能偶掌握这几个问题。
问题：
1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如何算环的长度？
3、如果链表为存在环，如何算柄的长度？
第一问是否有环就用快慢指针，fast=fast->next-next,slow=slow->next;代码如下
- bool IsExitsLoop(slist *head)
- {
- slist *slow = head, *fast = head;
- while ( fast && fast->next )
- {
- slow = slow->next;
- fast = fast->next->next;
- if ( slow == fast ) break;
- }
- return !(fast == NULL || fast->next == NULL);
- }
这样就可以判断是否有环路
第二问
首先引入一个图，
链表存在环，则fast和slow两指针必然会在slow对链表完成一次遍历之前相遇，证明如下：
slow首次在A点进入环路时，fast一定在环中的B点某处。设此时slow距链表头head长为x，B点距A点长度为y，环周长为s。因为fast和slow的步差为1，每次追上1个单位长度，所以slow前行距离为y的时候，恰好会被fast在M点追上。因为y<s，所以slow尚未完成一次遍历。
fast和slow相遇了，可以肯定的是这两个指针肯定是在环上相遇的。此时，还是继续一快一慢，根据上面得到的规律，经过环长s，这两个指针第二次相遇。这样，我们可以得到环中一共有多少个节点，即为环的长度。
简言之：第一次相遇后，继续按照2 1的步数走，再次相遇时，slot走的步数为环的长度。
第三问，求柄的长度：
有人对fast和slow的步长作了不同的设置来改善算法的效率，其实采用别的步长有可能使两指针无法在完成第一次遍历之前相遇，因此步长1和2是一个最优的选择。
假设slow行进了x并在A点进入环路时，fast在环中已经行进了n圈来到B点(n>=0)，其行进距离为2x，则可得到如下等式：2x = x +ns+s-y，做一下运算，即x=(n+1)s-y
若此时再设置一个指向头节点的指针p，而slow在M处，当p行进了x来到A点时，M行进了x=(n+1)s-y，恰好也来到A处，此时，2个指针相遇了。走的步数即为x长度可知。
简言之：第二次相遇后，fast指针指向head ，按照步长1走，slow指针继续走，知道fast==slow的时候，走的步数就为柄长度x的长度。
算法如下：
- slist* FindLoopPort(slist *head,int & cir_length,int & bing_length)
- {
- slist *slow = head, *fast = head;
- while ( fast && fast->next )
- {
- slow = slow->next;
- fast = fast->next->next;
- if ( slow == fast ) break; //判断有环
- }
- if (fast == NULL || fast->next == NULL)//判断有环
- return NULL;
- cir_length = 0; //环长度
- while ( fast ！= slow )
- {
- slow = slow->next;
- fast = fast->next->next;
- length ++;
- }bing_length = 0; //环长度
- fast = head;
- while (slow != fast) //再次相遇
- {
- slow = slow->next;
- fast = fast->next;
- bing_length ++;
- }
- return slow;
- }
经过这些代码后，希望能对链表求环的问题有一个更深入的了解。
扩展问题：
判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
比较好的方法有两个：
一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。