链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出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;
    }
}