快慢指针和找环入口_快慢指针为什么可以找到入口

作者：从前慢现在也慢 | 2024-07-28 18:03:59

踩

快慢指针为什么可以找到入口

用快慢指针的方式应该经过面试准备的人都知道了。

那么怎么找环的入口呢。

假设从链表开始的位置到环入口的距离为p，慢指针在环内走了的距离为c，假设慢指针一共走了n步，快指针一共做了2n步。

那么，有p+c=n

显然，从p+c这一点开始，慢指针再走n步，必然还会回到这个点。为啥？【因为经过了2n步，快指针到达了这一点，所以慢指针如果再走n步，也会到达这一点】

如果让快指针从链表头开始走n步，也会到达p+c这个位置，二者相遇的第一个地方，肯定是环入口。

看图

图里，AB=p，BD=c，由于慢指针走了n步，快指针走了2n步，所以慢指针再走n步还是到达D点。

【DB=c只是说，慢指针在环内走了c这么远，不一定是不到一圈，也可能慢指针在环内走了几圈之后才到达D点，此时我们假定BD长度是这路径的总长为c】

所以，得到如下解决办法：

在快慢指针相遇之后，让快指针重新指向链表头，慢指针还在p+c位置，然后二者同时走p步，每次走一步。走完之后二者相遇的位置就是环入口了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/895241