可以算作是一道谜语题
第一步仍然使用快慢指针法，找到第一次相遇点。
第二步设两个指针，一个从相遇点出发，另一个从原始起点出发，二者都是一次一步，当二者相遇时，所在的点即为环的入口.
第二步要会从数学上证明：
设进入环之前的直线距离为d，二者相遇时，慢指针在环上走过的距离是x，快指针绕环k（注意k必然>=1)圈外加x, 环的周长是C，则有:
d+x = (x+d+kC) / 2 => d+x = kC => d = (k-1)C+(C-x)
因此，第二步中，从起点出发的指针走过d时，从相遇点出发的的指针走过(k-1)C +(C-x)，而C-x恰好是回到入口点出的长度，于是得证。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *detectCycle(ListNode *head) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* p1 = dummy; ListNode* p2 = dummy; bool mark = false; while (p2!=NULL && p2->next!=NULL) { p1 = p1->next; p2 = p2->next->next; if (p1 == p2) { mark = true; break; } } if (mark == false) return NULL; int cnt = 0; p2 = dummy; while (p2 != p1) { p2 = p2->next; p1 = p1->next; ++cnt; } return p1; }};
