参考资料：
[1]本页思路
关键词：
2x=x+n
链表有环，长啥样：
一个链表中包含环
思路：
第一个，找环中相汇点。有两个指针分别指向头结点p1、p2。p1每次移动一步，p2每次移动两步。直到他们相汇p1=p2。比如他们相汇于5。p2实际上比p1多走了一个环，设p1走了x,则p2走了2x,环中的节点数为n，则x+n=2x。所以p1实际上走了一个环。
第二个，找环中的入口节点。p1保持保持位置不变。p2回到链表的起点。现在p1和p2每次都走一步,直到p1=p2。那么此时p1为入口节点。
疑问：
注意需要判断链表是否包含环
自己的代码:
再次改进版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
//如为空节点或者是一个节点的话，那么返回空节点
if(pHead == nullptr || pHead->next == nullptr)
return nullptr;
ListNode* pNode1 = pHead;
ListNode* pNode2 =pHead;
do {
pNode1= pNode1->next;
pNode2= pNode2->next->next;
}while((pNode1 !=pNode2) && (pNode1 != nullptr) && (pNode2 != nullptr) && (pNode2->next !=nullptr));
//判断是否是有环
if((pNode1 == nullptr) || (pNode2 == nullptr) ||(pNode2->next == nullptr))
return nullptr;
pNode1=pHead;
while(pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
};
