链表中环的入口结点

方法一：使用一个HashSet，遍历链表，当出现重复节点即有环，立即返回

import java.util.*;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null)
            return pHead;
        Set<ListNode> set = new HashSet<>();

        while(pHead != null){
            if(set.contains(pHead)){
                return pHead;
            }
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
}

方法二：快慢指针

分析：根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null)
            return pHead;
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast != null){
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next.next;
            }else{
                return null;
            }

            if(slow == fast){
                ListNode ptr = pHead;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }