循环链表：快慢指针进阶：找入口

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;
    }
}