判断链表是否有环，如果有返回环的入口，即链表有环证明，和找到环的入口证明（非常清晰的证明过程）_证明链表有环

有环链表

判断一个链表有环，如果有环，返回起点

使用快慢指针的方式，两个指针同时指向头节点，慢指针low一次走一步，快指针fast一次走两步，只要low和fast相遇即说明链表有环

只要快指针和慢指针有相差的步数，但最好是差一步，fast就可以追上low，不一定是low1步，fast2步

如果链表有环，此时fast指针比low指针多走了一倍的路程，此时fast重新指向头节点，low和fast都每次向下走一步，low和fast再次相遇的节点，就是环的入口 为什么？

证明：以下图为例，设在入口前的长度为preLen low与fast 的碰撞点位置为impact 入口位置到碰撞点位置的长度为 impPreLen 从碰撞点到入口的距离为 impProLen ,环的长度为 ringLen, 同时意味着 ringLen = impPreLen + impProLen => impPreLen = ringLen - impProLen

1. 以fast指针走两步，low指针走一步证明
2. 设 ： fast指针一共走了 fastN 步， low指针走了lowM步 ，并且fastN = 2lowN
3. 设：fast指针在环中走了fastRing圈，low指针走了lowRing圈（没到一整圈不算）
4. 此时fastN = preLen + fastRing * ringLen + impPreLen (入口前长度 + 走的圈数 + 最后入口到碰撞点长度)
5. lowN = preLen + lowRing * ringLen + impPreLen

可以推理出

1. preLen + fastRing * ringLen + impPreLen = 2 * (preLen + lowRing * ringLen + impPreLen)
2. fastRing * ringLen = preLen + 2 * lowRing * ringLen + impPreLen
3. preLen = (fastRing - 2lowRing) * ringLen - impPreLen
4. impPreLen = ringLen - impProLen 带入公式
5. preLen = (fastRing - 2lowRing) * ringLen - ringLen + impProLen
6. preLen = (fastRing - 2lowRing - 1) * ringLen + impProLen

根据推理公式可以看出preLen 的长度 = 碰撞点 + n(fastRing - 2lowRing - 1)个环完整圈数

同时 碰撞点出发走n(fastRing - 2lowRing - 1)个环完整圈数 在走一个 impProLen 长度，是正好到达环入口点的

所以最后 fast恢复到 1 步 是走 preLen 长度到入口点是，一定可以和 low指针相碰

public static Node isHasRollLinkedList(Node node) {

    if (node == null || node.next == null || node.next.next == null) {
        return null;
    }

    Node fast = node.next;
    Node low = node.next.next;
    while (fast != low) {
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        fast = fast.next.next;
        low = low.next;
    }

    fast = node;
    while (fast != low) {
        fast = fast.next;
        low = low.next;
    }
    return low;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23