解析

先通过快慢指针判断有无环

无环

直接返回null

有环

假设起点到环起点的距离是a，环的长度是k，且此时A、B在距离环起点x距离处相遇。

即慢指针再走x步就到达环的入口，此时slow走过的距离

a + nk + (k - x)

  
 

  
1
 

快指针走过的距离：

a + mk + (k - x)

  
 

  
1
 

由快慢的定义可知：

a + mk + (k - x) = 2 * (a + nk + (k - x))

  
 

  
1
 

化简得：

 a = (m - 2n -1)k + x

  
 

  
1
 

可知a为k的整数倍加x，而AB相遇的位置再走x步恰是环入口，所以此时让其中一个指针指向起点，然后同步走，一定能在环入口相遇！

所以可得代码：

package com.javaedge;

/**
 * @author JavaEdge
 * @date 2021/8/17
 */
public class DetectCycle {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isCircled = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                isCircled = true;
                break;
            }
        }
        if (!isCircled) {
            // 无环
            return null;
        }

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

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

文章来源: javaedge.blog.csdn.net，作者：JavaEdge.，版权归原作者所有，如需转载，请联系作者。

原文链接：javaedge.blog.csdn.net/article/details/119739155