给定一个单链表，只给出头指针h：

1、如何判断是否存在环？

2、如何知道环的长度？

3、如何找出环的连接点在哪里？

4、带环链表的长度是多少？

5、如果存在环，求出环上距离任意一个节点最远的点（对面节点）；

6、（扩展）如何判断两个无环链表是否相交；

7、（扩展）如果相交，求出第一个相交的节点；

解法：

1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

2、如果存在环，求环上节点的个数：

对于这个问题，我这里有两个思路（肯定还有其它跟好的办法）：

思路1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数；

思路2： 从碰撞点p开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次项目，此时经过的步数就是环上节点的个数 。

3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

该定理的证明可参考：

4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度（链表长度L = 起点到入口点的距离 + 环的长度r）

5、求出环上距离任意一个节点最远的点（对面节点）

如下图所示，点1和4、点2和5、点3和6分别互为”对面节点“ ，也就是换上最远的点，我们的要求是怎么求出换上任意一个点的最远点。

对于换上任意的一个点ptr0, 我们要找到它的”对面点“，可以这样思考：同样使用上面的快慢指针的方法，让slow和fast都指向ptr0，每一步都执行与上面相同的操作（slow每次跳一步，fast每次跳两步），

当fast = ptr0或者fast = prt0->next的时候slow所指向的节点就是ptr0的”对面节点“。

为什么是这样呢？我们可以这样分析：

如上图，我们想像一下，把环从ptro处展开，展开后可以是无限长的（如上在6后重复前面的内容）如上图。

现在问题就简单了，由于slow移动的距离永远是fast的一般，因此当fast遍历玩整个环长度r个节点的时候slow正好遍历了r/2个节点，

也就是说，此时正好指向距离ptr0最远的点。

对于问题6（扩展）如何判断两个无环链表是否相交，和7（扩展）如果相交，求出第一个相交的节点，其实就是做一个问题的转化：

假设有连个链表listA和listB，如果两个链表都无环，并且有交点，那么我们可以让其中一个链表（不妨设是listA）的为节点连接到其头部，这样在listB中就一定会出现一个环。

因此我们将问题6和7分别转化成了问题1和2.

看看下图就会明白了：

针对问题6还可以思路：

1、判断两链表最后一个节点是否相同，如果相交，则尾节点肯定是同一节点。

时间复杂度O（（length（A）+ length（B））、空间复杂度 = O（1）（存储最后结点的地址）

2、人为构环，如上图。将链表A的尾节点指向链表B，如果B链表有环，则两个链表相交，此时从链表B的头指针往下遍历，如果能够回到B，则说明相交

时间复杂度O（（length（A）+ length（B）），没有额外的空间消耗

针对问题7（无环相交）：

1、先取得两个链表A和B的长度len（A）和len（B）

2、沿着A和B链表中较长的链表遍历，使用指针追赶的方法。

设定两个指针fast（长链表）、slow（短链表上）。fast在较长链表先出发前进(lengthMax-lengthMin)步（即是二者的长度之差）使fast和slow指针到相交点的距离相等，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

判断是否存在环的程序：

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);  }

寻找环连接点（入口点）的程序：

slist* FindLoopPort(slist *head)  {      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;        slow = head;      while (slow != fast)      {           slow = slow->next;           fast = fast->next;      }        return slow;  }