要先判断一个链表是否有环，最常用的方法是双指针法。
想象一下，如果两个人在环形赛道上跑步，那么不管他们之前的起点位置如何，跑得快的必将与跑得慢的相遇。在该题中，直接使用快慢指针，慢指针步长为1，快指针步长为2，如果出发后某一时刻快慢指针相遇，那么就说明链表带环。程序如下：
ListNode *detectCycle(ListNode *head) {
ListNode *fast=head;
ListNode *slow=head;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)break;
}
if(fast==NULL||fast->next==NULL)return false;
return true;
}
快慢指针相遇后，假设相遇点为M，如果继续向前走，不难想到，下一次相遇点依然是M（画一个环试一下就知道了），而且第二次相遇时，快指针走过两圈，慢指针走过一圈，然后在M点相遇。因此，当快慢指针相遇后，二者继续往前走，当再次相遇时，慢指针走过的长度即是环的长度。
int *lenOfCycle(ListNode *head) {
ListNode *fast=head; //快指针
ListNode *slow=head; //慢指针
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)break; //快慢指针相遇则退出，
}
if(fast==NULL||fast->next==NULL)return NULL;
slow=slow->next;
fast=fast->next;
int len=1;
while(slow!=fast) //快慢指针继续往前走
{
slow=slow->next;
fast=fast->next;
len++;
}
return len;
}
如图所示。
假设链表起点为A，环入口为B，快慢指针在C处相遇，且从A到B距离为X，B到C距离为Y，环的长度为L，那么就有以下结论：
相遇时慢指针则走了X+Y，快指针走了2*(X+Y)， 由于相遇，则有：2*(X+Y)-(X+Y)=K* L，其中K=1,2,3… 即
X+Y=K * L 变形可得： X=L-Y+(K-1)*L这个式子就很重要了，表示什么意思呢？
这说明X的这段距离，就等于先走L-Y的距离，然后再走K-1次L的距离之和，而这里的L就是环的长度，因此，这个式子又可以看作是X的这段距离相当于先走了L-Y的距离，然后再绕环转了K-1圈。那么X和L-Y分别表示什么呢？看看图就明白了：X表示从A到B的距离，而L-Y刚好是从C到B的距离(图中逆时针)，也就是说，一个人从A开始走，一个人从C开始沿逆时针走，那么从C开始走的这个人会经过绕环K-1圈后在B处与从A处触发的人相遇，而B点就是不仅是相遇点，还更是环的入口。
因此，找到环的入口的办法是：定义一个新的指针从链表起点开始走，同时前文中的慢指针从相遇点继续往前走，当新指针和慢指针相遇时，这个相遇点就是环的入口了。
代码如下：
ListNode *detectCycle(ListNode *head) {
ListNode *fast=head; //快指针
ListNode *slow=head; //慢指针
ListNode *slow2=head; //新指针
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)break; //快慢指针相遇则退出，
}
if(fast==NULL||fast->next==NULL)return NULL;
while(slow!=slow2) //新指针从起点出发，慢指针从相遇点出发
{
slow=slow->next;
slow2=slow2->next;
}
return slow;
}
前面说了求环的长度和环的入口的方法，那么新指针从头到环的入口的长度再加上环的长度，结果自然就是链表总长了。