算法求解!如何判断一个单向链表是否有环路?

star55

用拓扑排序就行了

即去枝叶方法。一般的数据结构都会有介绍，看看就明白了，在这边我也将不清楚，还是书比较容易说明问题，呵呵

mfmain

大家把问题复杂化了，一般说来应该步长分别为1和2是最优算法，问题可以简化为时针和分针的相遇问题，假设时针和分针每步都走一格的整数倍，显然如果步长分别为1和2，则能保证在一圈之内肯定相遇，而其他情况除非瞎猫正好蹦到死耗子，否则...

mfmain

sorry, 刚才分析的不对，假设步长为a,b，进入圈之前长度为m，圈长n，实际上，不论步长为多少（只要不相同），圈内相遇的步数都不会超过n步，我们重新分析效率问题：
双方都进入圈需要：m/min{a,b}步
最差情况下圈内相遇的步数：n/最大公约数{a,b,n}
事实上，因为n是随机的，因此圈内相遇的步数也是随机的，不可控制，但上限是n步，所以应该尽量减小双方进入圈需要的步数，所以a,b越大越好，但又产生了另外一个问题，就是步长越长，走一步所花的时间就越长，所以是两难！

YeLLoW

学习中，非常感谢

jiangchun_xn

普通算法:时间复杂度O(n^2)
变步长算法时间复杂度接近O(n)
的确算法非常漂亮,

但是无论哪种数据结构本身就应该满足这种数据结构的逻辑意义,因此,对于出现中间环的链表本身就是发生了错误,说明链表的操作中发生了错误.(单向链表不应该提供尾指针随意指向的方法)

如果在实际中会发生这种情况,这就说明用单向链表这种数据结构就是不合适的.这种结构应该是多入单出,可以证明这样的环只会存在一个.(可以用数学归纳法),这样维护这个结构可以在链表之外维护一个bool变量circled,并且提供一个方法,就是设置尾指针制向,同时修改circled,这样,查找是否有环的时间复杂度为o(1).

其实我并不是说这个算法不好，相反,这个算法非常精妙,但是,我个人认为数据结构更重要的是如何选择合适的数据结构和严格的应用数据结构.

aero

你的意思是要用另一个变量来对应链表尾指针的NULL与否？当circled是false的时候，要记得去把尾指针置NULL，然后把circled置true？

如果这个程序员能记得去置circled为true，那他自然就会记得将尾指针置成NULL了。而他记得将尾指着置成NULL，却未必能记得将circled置成false。

觉得加的这个变量是蛇足，没有任何意义！链表自然是不应该出错的。但是一旦他里面有了环，怎么能保证和链表一同维护的circled是可信的呢？

jiangchun_xn

原帖由 "aero" 发表：
你的意思是要用另一个变量来对应链表尾指针的NULL与否？当circled是false的时候，要记得去把尾指针置NULL，然后把circled置true？

如果这个程序员能记得去置circled为true，那他自然就会记得将尾指针置成NULL了。..........

的确circled有点多余( )

我的意思是链表不应该出现环(除了头尾相连的为了方便的链表),链表提供的所有方法均不应该产生环.产生环就说明发生了 意外 的错误.

comepu

楼主的算法错了吧？

cjaizss

我曾经想到的时间复杂度o(n)，空间复杂度o(1)的算法和flw说的不一样
当然，flw这个算法我也知道
不过后来想想，本质也还是一样

[ 本帖最后由 cjaizss 于 2006-4-6 13:06 编辑 ]

luojiannx

原帖由 yangtou 于 2004-9-20 16:15 发表
不需要两个步长互素，只要步长不同就可以。

错了

步长１，６
你自己找个循环圈子是５步长的例子吧
你将发现６的那个可以有可能永远在１的前面２位

两者可以永不相遇