解析
先通过快慢指针判断有无环
无环
直接返回null
有环
假设起点到环起点的距离是a，环的长度是k，且此时A、B在距离环起点x距离处相遇。
即慢指针再走x步就到达环的入口，此时slow走过的距离
a + nk + (k - x)
快指针走过的距离：
a + mk + (k - x)
由快慢的定义可知：
a + mk + (k - x) = 2 * (a + nk + (k - x))
化简得：
a = (m - 2n -1)k + x
可知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; } }
