（图文结合）利用快慢指针判断链表中是否有环和找出环的入口结点的原理剖析_使用快慢指针法为什么可以判断两个链表是否有环

作者：Guff_9hys | 2024-07-28 18:05:21

踩

使用快慢指针法为什么可以判断两个链表是否有环

首先假设有一个无限长的链表，其中slow指针指向链表的第N个结点（结点从0开始），fast指向第0个结点，那么此时fast与slow的距离为N-0=N。

接下俩采取slow和fast分别采取一次一步和两步的策略移动，设k为移动次数，当k=1即一次移动后则slow与fast距离变为N+1-2=N-1

继续移动，其总的距离变化：N、N-1、N-2...2、1、0（相遇）

当移动k=N时即移动N次后，fast与slow距离变为0，相遇；

理解了这个，我们再看一个带环链表，其中的环等价于一个无限长的链表，当slow进入环时，fast总会在环中的某个位置。</

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