解析
先通过快慢指针判断有无环
无环
直接返回null
有环
假设起点到环起点的距离是a，环的长度是k，且此时A、B在距离环起点x距离处相遇。
即慢指针再走x步就到达环的入口，此时slow走过的距离
代码语言：javascript复制a nk (k - x)快指针走过的距离：
代码语言：javascript复制a mk (k - x)由快慢的定义可知：
代码语言：javascript复制a mk (k - x) = 2 * (a nk (k - x))化简得：
代码语言：javascript复制 a = (m - 2n -1)k x可知a为k的整数倍加x，而AB相遇的位置再走x步恰是环入口，所以此时让其中一个指针指向起点，然后同步走，一定能在环入口相遇！
所以可得代码：
代码语言：javascript复制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;
}
}
