环链表入口_环形链表的入口

作者：不正经 | 2024-05-21 21:41:56

踩

环形链表的入口

快慢指针：一个每次前进一步，一个每次前进两步。
显然，若存在环结构，则两指针一定相遇，且快指针经过一圈后在换种某处与慢指针相遇。
此时，设置一个新的指针，从头节点开始出发，保持与慢指针相同的速度，最终相遇点即为环结构入口。
证明：假设s1-s2-s3-s4长度为a、b、c(s3为相遇点)，
则slow走过的距离：a+b， fast走过的距离：a+b+(b+c)
根据快慢指针定义可得：2*(a+b) = a+b+(b+c)==>a=c
则此时只需要一个指针从头节点出发，保持与慢指针相同速度，最后相遇点即为环入口。

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