image.png

思路

快慢指针解法

1. 定义两个指针fast和slow, 每次让fast走两步, slow走一步, 当fast和slow相遇时,证明链表有环

2. 如果求环的入口节点呢

   
   
   image.png
3. 假设链表头节点 到环的入口要走x步, 环入口到 fast和slow相遇的点位y, 相遇点y到环入口为z
4. 可以推到出如下公式 slow 到相遇点 = x + y, fast到相遇点= x + y + n(y + z) , n(y + z) 表示fast在环内多跑的若干圈数
5. fast是slow的两倍速度 2(x + y) = x + y + n(y + z)
6. 两边抵消掉一个 (x + y) 得结果 x + y = n (y + z)
7. 需要找到环形的入口, 就是我们求的是x的值, 将x单独放到左边 x = n(y + z) - y;
8. y + z 表示理解为走一圈需要多少步
9. 从n(y + z) 分出一个 y + z来, 即分离出一圈来, 整理后的公式: x = (n-1) (y + z) + z 这里注意n一定是大于等于1
   因为 fast至少要走一圈才能和slow相遇, 这里还可以理解为无论fast在环内走几圈都一样, 假设n =1(一圈) n(y + z) = 1 * (y + z ) = y + z
   x = (n-1) (y + z) + z 上面的公式就化解为 x = z; 所以求出z的值即可
10. 定义两个指针index1 = head 指向头节点, index2 = slow 指向相遇节点y, 同时向前每次走一步, 当index1 和 index2相遇时, 就是z的值, 即环形链表入口的节点

    public static ListNode detectCycle1(ListNode head) {
        ListNode fast, slow;
        fast = head;
        slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode index1 = head;
                ListNode index2 = slow;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }