给定一个单链表：

1. 如何判断单链表是否有环？
2. 如何找出环的连接点在哪里？
3. 如何知道环的长度？

使用追赶的方法，很容易得到环的存在性结论。能够解决问题1。记下碰撞点P。
从碰撞点P重新开始追赶操作，再次碰撞。中间经过的操作数就是环长。解决问题3。
分别从碰撞点P和链表头，同步地步进扫描，直到碰撞。此次碰撞点就是链表连接点。解决问题2。

问题2的证明如下：

链表形状类似数字 6 。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。

分析追赶过程。
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。

连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。

根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。
而，同为前进 a 步，同为连接点，所以必然发生碰撞。

综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。

问题2 知道环的长度s，那么p1从链表的头开始，p2开始指向p1的第s个后继结点,p1 p2同步往前移动，当p1==p2时，p1指向的就是环的开始。

问题3 after p2 catches p1, let they continue going forward, and count the number of nodes p1 visits (n1). When p2 catches p1 again, n1 is the size of loop.

可在”Ge Chunyuan“的方法上加以改进：
1、逆转链表List，若逆转后的头指针与原链表指针相同，则有环，否则无环。若要恢复链表List再逆转一次即可。
2、在逆转链表List的同时，用一双端队列A记录各个节点地址，并计数；在有环的情况下，从队列两端取出节点地址(A[i]、A[j])进行比较，若A[i]==A[j]继续，若A[i]!=A[j]则说明前一节点A[i-1]（或A[j+1]）即为环的连接点，环的长度即为j-i+2

做个友情连接，^-^
http://qinchong637.javaeye.com

判断是否有环。

bool checkLoop(List head)
{
List p1 = head;
List p2 = head;

if (p1 == NULL || p1->next == NULL)
{
   return false;
}   

while(p2 && p2->next)//改成这个样子
{
   if (p2 == p1)
   {
      return true;
   }
   p1 = p1->next;
   p2 = p2->next->next;
}

return false;
}

第二个问题，只要在return true的那个地方 return 那个节点就可以了，那个节点就是连接点了。

我也写个答案

typedef struct LinkedList
{
    int data;
    LinkedList* pNext;  
}LinkedList;

/**
* test 6, write a function to check whether there is loop in a linked list
* @param pList [input] linked list
* @return bool, if there is loop inside, return true, otherwise false
*/

bool isExistLoop(LinkedList* pList) 
{
    if (pList == NULL || pList->pNext == NULL)
        return false;

    LinkedList* p1 = pList;
    LinkedList* p2 = pList;


    while (p2 != NULL && p2->pNext != NULL)
    {
        p1 = p1->pNext;
        p2 = p2->pNext->pNext;

        if (p1==p2)
            return true;
    }
    return false;
}

在搞一个破坏性的想法 如果原来的链表是1->2->3->4>5->6->7->8->5这样一个有环的链表 我们可以这样 1.翻转链表 同时记录下整个链表的翻转长度S 并得到翻转以后的链表 1->2->3->4->5 2.遍历链表1->2->3->4->5 得到长度a 3.如果S=a没事， 如果s>a,显然有环，环的入口点在5整个节点。而且环的长度是S-2*a; 这样的效率也是不错的，就是要破坏原来的链表

这样如何：

int i, j;
void *backup[MAX];
void *tmp;
void *head = p;

for( i = 0; (p->next != head) && (p->next != NULL);){
tmp = p;
p = backup[i++] = p->next;
tmp->next= head;
}
if ( p == NULL ){
//printf("没上环. － －\n")
}
else{
for ( j = 0; backup[j] != p; j++ );
//1. printf("上环了 -,-\n")
//2. 环在这里---> p
//3. 环的size ---> i-j
}

使用backup，链表可以恢复。
上面只是算法思路，没处理细节，比如极端情况（就是1>2>3>1 这种纯环或空链表）

给定一个单链表：

1. 如何判断单链表是否有环？
2. 如何找出环的连接点在哪里？
3. 如何知道环的长度？

答:
1. 用一个哈希表，用O(n)的时间和空间复杂度解决。从第一个节点开始，把节点放入表。如果这个节点已经在表里，那么说明有环。上面的答案都是至少O(n^2)时间的。
2. 连接点在重复的位置。
3. 把哈希表改成Map<Node,int>。int是当前的位置。如果出现重复k，那么环的大小为当前位置i-k+1。