剑指Offer——链表中环的入口结点

题目描述：

一个链表中包含环，请找出该链表的环的入口结点。

分析：

设置两个指针p1，p2，

两个指针都从链表的头部开始走，不过p1每次走一步，p2每次走两步。

直到相遇的时候，p2走的长度是p1的两倍。

此时让p2从头开始走，p1继续往下走，不过此时两指针都是一步一步走。

再次相遇的地点就是环的入口。

证明：

假设结点数一共有m个，环中的结点数有n个。

第一次相遇的时候，它们肯定是在环中相遇的，p1走了s1步，p2走了2*s1步。

那么此时它们在环中的位置是一样的，即(s1-(m-n))%n=(2*s1-(m-n))%n，

也就是s1-(m-n)和2*s1-(m-n)同余，充要条件是(2*s1-(m-n))-(s1-(m-n))是n的整数倍，即s1是n的整数倍。

此时如果让p1再走(m-n)步，那么p1将停在环的入口处，因为p1一共走了m+n*k的步数。

那么我们此时让p2从起点开始一步一步走，到达环的入口也是(m-n)步。所以此时它们会在环的入口处相遇。

代码：

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     ListNode* EntryNodeOfLoop(ListNode* pHead) {
13         ListNode* p1 = pHead;
14         ListNode* p2 = pHead;
15         while(p2 && p2->next) {
16             p1 = p1->next;          // p1走一步
17             p2 = p2->next->next;    // p2走两步
18             if(p1 == p2) {          // 相遇的时候，p2的步数是p1的两倍
19                 p2 = pHead;         // 让p1又从头开始走
20                 while(p1 != p2) {   // 现在p1和p2都一步一步走，直到他们相遇，相遇的位置就是环的入口
21                     p1 = p1->next;
22                     p2 = p2->next;
23                 }
24                 return p2;
25             }
26         }
27         return NULL;
28     }
29 };