链表中环的检测

作者：盐析白兔 | 2024-02-06 20:50:45

踩

链表中环的检测

一、查找是否存在环

1. 定义两个快慢指针 pFast 和 pSlow，pFast 每次走两步，pSlow 每次走一步。

如果 pFast 在循环遍历后为 null，则链表中不存在环。

如果 pFast 和 pSlow 相遇则链表中存在环。

2. 为什么 pFast 和 pSlow 会相遇呢？

假设存在环，那么快指针与慢指针终究会进入同一个环中，那么必定会形成下面三种情况之一：

(1) 快指针与慢指针之间差一步，此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇；
(2) 快指针与慢指针之间差两步，此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况;
(3) 快指针与慢指针之间差 N 步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差 (N + 1 - 2) -> N - 1 步，最后总会转化为情况一。

所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。

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