image.png
力扣142
image.png
如上图，判断是否为循环链表，和上一题一样，使用快慢指针即可。然后看一下怎么找循环入口点：
slow指针走过的节点数为: x + y
fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针
所以x + y = x + y + n (y + z)
最后化简：x = n (y + z) - y，我们首先要确定一点，就是慢指针走过的距离一定是x+y，因为快指针一定会在慢指针走完环形（即x+y）这个圈第一圈之前相遇，其次再确认一点，快指针一定不会跳过慢指针移动，因为快指针相对于慢指针一次只移动一个节点。
根据上述可以证明 x = n圈环形链表的长度 - y，那么类比运动会跑步，就是跑的快的甲和跑的慢的乙相遇的时候，
x = 甲跑了n-1圈 + z
那么如果去除环绕圆跑的距离，x = z。所以从相遇点到环形链表入口和起点到环形链表入口距离想等。
public class Solution {
public ListNode detectCycle(ListNode head) {
// 在此处写入代码
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;//快指针走两步
slow = slow.next;//慢指针走一步
if(fast == slow) break; //相遇代表有环
}
if(fast == null || fast.next == null)return null;
slow = head;//慢指针回到链表头部
while(fast != slow){
slow = slow.next;
fast = fast.next;//快指针也调整为一次走一步
}
return slow;
}
}
