其实这种题,感觉非常微妙。
想起之前做过如何判断有环,就是使用快慢指针,快指针fast一次走两步,慢指针slow一次走一步,只要有环,就一定会相遇。
汗当时没啥思路,而且听别人讲课这样讲,跟着做了这道题,但想想自己并没有思考什么……如果大家做这个的时候,请多多想想它隐藏的条件。

首先明确的是,只要有环,快慢指针就会相遇
上面说到,快指针fast一次走两步,慢指针slow一次走一步,可以得知快指针走的步数(或者说快指针经过的结点数)是慢指针的两倍,可以得知fast = 2 * slow
分析一种普通的情况:
从数学的角度,假设它们在x处相遇,还没进入环的部分长度为a,进入环后,(按指针顺序遍历)从入环的第一个结点到x的长度为b,从x再回到入环的第一个结点的长度为c。
又设,慢指针到达相遇点x,经过a+b这么长,有slow = a + b,快指针追上慢指针,一定是在环上比它多走一圈,即fast = a + b + c + b
综合重点的三条式子得知,a == c
所以在相遇点处,走未入环部分的长度a,即可找到入环的第一个点。

PS:上面的假设只是从一个狭隘的角度来分析,真正使用数学公式来推导的话我还没有这个能力……它是普遍情况中的一种特殊情况,结论没有错,但过程有多种。
比如,未入环的长度a非常大,而环的长度b+c很小,那就会导入fast = a + n(b + c)……

下面展示一下代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        // 找交点
        do{
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }while(fast != slow);
        // 总会相遇!因为a == c,即未入环长度与相遇点距第一个交点的长度一样
        while(fast != head){
            fast = fast.next;
            head = head.next;
        }
        return head;
    } 
}

我想给它加个标签:数学。