题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
时间限制：1秒 空间限制：32768K
解题思路
1、暴力解题：使用HashSet将不重复的结点加入，重复结点直接返回即可
import java.util.HashSet;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
HashSet<ListNode> hs=new HashSet<>();
while(pHead!=null){
if(hs.isEmpty()||!hs.contains(pHead)) hs.add(pHead);
else return pHead;
pHead=pHead.next;
}
return null;
}
}
2、使用前后指针
见链表中环的入口结点
判断环是否存在。两个速度不同的指针（fast和slow）从起点出发，如果有环则必定会相遇，若fast指向null则不存在环
找到环的入口。两指针第一次相遇后，让一个指针从头结点，另一个指针从相遇结点，以相同速度开始移动，再次相遇的结点即为环的入口结点。
假设存在环，fast以速度2运行，slow以速度1运行，证明如下：
（1）slow第一次移动到环入口结点时。如图所示
a为起点h到环入口t的距离；m1为slow首次到环入口t时fast的位置；b为位置t到m1的距离；n为环的周长
此时，slow指针移动的距离为a，fast指针移动的距离为a+b+x*n（x为fast移动的圈数），由于fast的速度是slow速度的两倍，因此2a=a+b+x*n得出a=b+x*n
（2）两指针首次相遇时。
m2为两指针首次相遇的位置；
由于slow到达t位置时，fast离t位置逆时针的距离为n-b。两指针的速度差为1，因而需要n-b的时间才能相遇。此时slow移动的总距离为a+n-b。因此首次相遇点m2离环入口t的逆时针距离为b
（3）求环入口的办法。
由于第一次相遇点m2离环入口t的逆时针距离为b，因此指针只需要移动b+y*n的距离（y为移动的圈数）即可。此时由于起点h到环入口t的距离a=b+x*n，因此只需要将slow指针移动起点h处，fast指针仍然在相遇点m2处，让它们以相同速度移动，slow和fast相遇的结点就是环入口t
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode fast=pHead,slow=pHead;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast){
slow=pHead;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return fast;
}
}
return null;
}
}
