一、题目
函数原型：
struct ListNode *detectCycle(struct ListNode *head)
二、思路
要找到入环结点，就要计算头结点到入环结点之间的距离。
设链表环外的长度为a；慢指针与快指针相遇时，它们逆时针到入环结点的距离为b，顺时针到入环结点的距离为c，那么链表中环的长度就是b+c。
当慢指针与快指针相遇时，设快指针已经在环内走了n圈。由于快指针走过的距离始终是慢指针的两倍，因此a+b+n(b+c)=2(a+b)，即a=c+(n-1)(b+c)。
有上述式子可得，头结点到入环结点间的距离就等于快、慢指针相遇位置顺时针到入环结点的距离再加上（n-1）环的长度。
因此，如果设置一个遍历指针从头结点开始遍历，它与慢指针相遇时的位置就是入环结点位置。
三、代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow=head; struct ListNode *fast=head; int answer=0;//判定有无环的标志 while(fast&&fast->next) { fast=fast->next->next;//快指针一次走两步 slow=slow->next;//慢指针一次走一步 if(slow==fast)//快慢指针相遇 { answer=1; break; } } if(answer==0)//找到了空结点，说明链表无环 return NULL; else//链表有环 { struct ListNode *cur=head;//遍历指针，从头结点开始遍历 while(slow!=cur)//找遍历指针和慢指针相遇的位置 { cur=cur->next; slow=slow->next; } return cur;//找到并返回入环结点 } }
