判断链表是否存在环的算法理解的问题

来源：百度知道 编辑：UC知道 时间：2024/05/11 04:00:56
题目：怎么判断链表是否有环！（环有6形和0形）
回答：定义两个指针，同时指向头，然后一个指针向后移一步，一个移二步，经过n次后，如果2个指针又指向同一个节点，则有环

-----------------------------------------------------------------
我不明白的是为什么上面能确实有环，怎么知道如果存在环两个指针就会相遇？
跑步能追上确实很容易理解

但问题是，跑步是连续的，而这里不是

因为有一个指针是跳两步的，不是连续的，怎么证明这样也肯定能碰上？好像只能证明一定能超过啊？

还有，这道题如果改成不知道链表的头，只知道其中的一个指针，还能不能做？要怎么做？

谢谢

你画上一个圈就知道啦!速度快的开始肯定会超过慢的.
然后一次追上一个单位,如果确实是个圈的话肯定会追上并且是相遇在同一个单位之内!
所以是一个移一步，另外一个移二步!

因为有一个指针是跳两步的，不是连续的，怎么证明这样也肯定能碰上？好像只能证明一定能超过啊？
-----------------------
一个速度是2,一个速度是1.它们之间的距离一次减少一个单位,超过的时候当然会相遇了

还有，这道题如果改成不知道链表的头，只知道其中的一个指针，还能不能做？要怎么做？
---------------------------------
可以~把指针头改成已知的那一节就可以了.

就是跑步理论
如果是环，跑的快的在最后一定能把跑的慢的套圈
当然结束的边界条件：
这个很简单
你一步一步走，不管怎么样，对方每次2步，是不可能错过的，试着走一遍就知道了

一个指针也是一个道理，记录这个指针，然后next，然后判断也是一样的

这样比喻吧：
两个人，先后进入环形跑道，不管进入之前两人的相对位置如何，只要一个跑得快，一个跑得慢，两个人在这个环形跑道上跑，跑得快的那个人，总能追上跑得慢的，是吧？

:)