关于leetcode算法:环形链表入口点证明leetcode142

首先须要应用 Floyd 判圈算法（又称龟兔赛跑算法）的快慢指针思维找到环内快慢指针相遇点 c。
如图所示：

假如终点为 a，环的入口点为 b。终点 a 到环入口点的间隔为 x，环的入口点到快慢指针相遇点间隔为 y。

从快慢指针相遇点将 慢指针往回倒退 y 步 达到点 b，因为快指针速度是慢指针的两倍，故快指针会倒退到 c ’ 点，其中 b 到 c ’ 的间隔也为 y。即当慢指针走到 b 点时，快指针的地位在 c ’。因为慢指针此时走了 x 步，故快指针从 a 走 2x 步达到了 c ’ 点。进而等价于 快指针从 b 点走 x 间隔会走到 c ’ 点。

因为 bc = bc’，故 从 c 点走 x 间隔会走到 b 点。a->b == c->b[当然 c 到 b 可能走了不止一圈]。

综上，当快慢指针相遇后，设置两指针 p1、p2，p1 终点为 a，p2 终点为 c，同时一走一步，当 p1 和 p2 相遇，即为环的入口点。p1、p2 可重用快慢指针。

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    } 
    if (fast == null || fast.next == null) return null;

    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}