1.问题描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
2.解决思路
2.1 思路1
1）先判断链表是否有环；
2）如果有环，假设环里面有n个结点，除去环之外有m个结点，使用快慢指针fast和slow，开始都指向头结点head，每次移动一个结点：
设fast指针先走x了步，我们希望slow指针从1结点经过m步到达第m+1个结点（即环入口）的时候，fast指针也正好到达了环入口，所以有如下关系：
总的结点数：n + m
到达环入口时，slow经过m+1个结点, fast 经过了n+m+1
(1+x) + m = n + m + 1——> x = n，即fast指针要先走n步。
所以需要做的关键事情：链表有环的情况下，统计链表里面的结点个数。
总结解决思路：
a）判断链表是否有环：快慢指针是否会相遇，相遇了，记下相遇点A。
b）从相遇点A开始，移动指针到再次回到A，以统计环中结点的个数n。
c）fast指针和slow指针指向head，fast先走n步，相遇时即为环入口。
2.2 思路2
如上图所示，假设相遇时候快指针fast（每次走2步）走了m圈环，慢指针（每次走1步）走了n圈环，相遇点在B，则有如下关系：
fast的路程：Sf = X + m * C + Y
slow的路程：Ss=X + n * C + Y
Sf = 2 * Ss ——> 2( X + n * C + Y) = X + m * C + Y——> X = (m - 2n) * C - Y = (m - 2n - 1) * C + (C-Y) = (m - 2n - 1) * C + Z
即环前面的路程 = 环的长度的整数倍（可能为0） + Z
所以总结思路2为：
1）先判断是否存在环；
2）有环：让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x），从相遇点开始走的那个指针也一定刚好到达环入口点。所以两者会相遇，且恰好相遇在环的入口点。
3.代码实现
3.1 思路1
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* head){
if(head==NULL || head->next == NULL)
return NULL;
//判断是否有环
ListNode* slow = head->next;
ListNode* fast = head->next->next;
ListNode* MeetNode = NULL;
while(fast != NULL && slow != NULL){
if(slow == fast) {
MeetNode = slow;
break;
}
slow = slow->next;
fast = fast->next;
if(fast != NULL)
fast = fast->next;
}
//统计环中结点的个数
if(MeetNode == NULL) return NULL;
int NumOfLoop = 1;
while(fast->next != MeetNode){
++NumOfLoop;
fast = fast->next;
}
//寻找环的入口
fast = head;
slow = head;
for(int i = 0; i<NumOfLoop; ++i)
fast = fast->next;
while(slow != fast){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
3.2 思路2
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* head){
if(head==NULL || head->next == NULL)
return NULL;
//判断是否有环
ListNode* slow = head->next;
ListNode* fast = head->next->next;
ListNode* MeetNode = NULL;
while(fast != NULL && slow != NULL){
if(slow == fast) {
MeetNode = slow;
break;
}
slow = slow->next;
fast = fast->next;
if(fast != NULL)
fast = fast->next;
}
//使用快慢指针
if(MeetNode == NULL) return NULL;
fast = head;
while(fast != MeetNode){
fast = fast->next;
MeetNode = MeetNode->next;
}
return MeetNode;
}
};
| 
转播
