题目描述
一个链表中包含环，请找出该链表的环的入口结点。
初步想法是每个节点做几个标记，表示是否被访问过，那么遍历链表的时候就知道哪个被访问到了。但是不会实现。
另一个直觉是判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。
容易知道，当1x的指针p1和2x的指针p2相遇时，p1走了x步，p2走了2x步，而p2比p1多走的，有两部分：(1)环内部，p1还没有走过的；（2）换内部，p1和p2重合的
这两部分加起来就是整个环。那么其实p2比p1多走的就是这么一个环的距离，也就是说：
2x-x = n ==> n=x
即：p1当前走了一个环长度的距离。
下图表示了p1和p2相遇在B点的情况，其中A点开始顺时针方向回到A的轨迹就是环形，长度为n。
不妨假设链表总长为L，那么：
CA+A环=CA+n=L ==>L-n=CA
CB=x=n=A环
==> BA弧=L-CB=L-n=CA
也即：BA弧=CA，那么指针p1从B继续走，而指针p2从链表起点C从新开始（但是步长这次取1），则当p2到达A点时，p1也到达A点。
对应到算法中，当1x和2x套圈时，p1和p2按照这个策略继续做while循环，直到再次相遇，就找到了环的入口。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead==NULL){
return NULL;
}
if(pHead->next==NULL){
return NULL;
}
ListNode* p1=pHead;
ListNode* p2=pHead;
while(p2!=NULL && p2->next!=NULL){
p1=p1->next;
p2=p2->next->next;
if(p1==p2){
p1 = pHead;
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}
if(p1==p2){
return p1;
}
}
}
return NULL;
}
};