回 帖 发 新 帖 刷新版面

主题:判断链表环路的原理?

读过好多书,里面对判断链表环路的方法一般都是说:维护两个临时元素指针,一个依次指向链表元素, 另一个依次指向链表的奇数个元素;判断这两个元素指向的元素是否相等,如果相等,则表示有环路,如果不相等,则表示没有环路。

我想问的是,这样做的原理是什么,为什么这么做就能查出是否有环路?怎么用数学理论证明?(虽然我早已知道这种方法是对的)

回复列表 (共3个回复)

沙发


还望高手赐教!!!

板凳

暂且称它为追赶法,

一个速度快,一个速度慢,如果有圈存在,总有赶上的时候,这个算法只限于内存不足的情况,复杂度不好。

3 楼

谢谢,解释得很生动。我搜索了一下,也有人把这种方法叫做 步长法。

我来回复

您尚未登录,请登录后再回复。点此登录或注册