1、前言

题目描述

2、思路

这个题目的思路是使用快慢指针，但是快慢指针相遇后，如果找到起点是一个问题。起点寻找的方式是：相遇后，将一个指针从头节点开始，一个指针从相遇的地方开始，他们相遇的地方是起点。

解法描述

证明如下：
相遇时：

slow走过的路程：x + y + n(y+z), n代表slow绕了n圈
fast走过的路程：x + y + m(y+z)，m代表fast饶了m圈
m > n

因为fast速度是slow两倍：

2(x + y + n(y + z)) = x + y + m(y + z)
x + y = (m - 2n)(y + z)
x = (m - 2n)(y + z) - y
y + z就是1圈，假设 o = m-2n，o是一个正整数，那么 x = o(y + z) -y
如果o = 1，那么 x = z，和答主假设的情况一样
如果o > 1，那么 x = (o-1)(y+z) + y + z - y, x = (o-1)(y+z) + z，即x的长度为o-1圈加上z

所以，从第一阶段获得的相遇点，走过x距离机会到达环的起点。

3、代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

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

        return null;
    }
}