题解 | 链表中环的入口结点

还是使用快慢指针，为什么快慢指针能够找到环的入口节点，这里需要用到数学的推导

假设：

• 从头节点到环入口的距离为 a
• 从环入口到相遇点的距离为 b
• 从相遇点走到环入口的距离为 c（即环的长度为 b + c）

在相遇时：

• 慢指针走过的距离：s = a + b
• 快指针走过的距离：f = a + n(b + c) + b （这里的 n 指的是在环内走了多少圈）

由于快指针的步幅是慢指针的2倍：

f = 2s => a + n(b + c) + b = 2(a + b)

即：

a = (n - 1)(b + c) + c

这意味着从头节点到环入口的距离 a，等于从相遇点绕环 n - 1 圈后再走距离 c。因此，一个指针从头节点开始，一个从相遇点开始，同步后移，一定会在环入口处相遇！

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean hasCycle = false;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) {
                hasCycle = true;
                break;
            }
        }

        // 没有环，直接返回null
        if(!hasCycle) return null;

        // 快慢指针相遇后，慢指针重新指向头节点
        // 让快指针和慢指针同时移动1步，相遇时的节点即为入口节点
        slow = pHead;
        while(slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}