一个关于单向链表的面试题。

emacsnw

原帖由 win_hate 于 2007-4-29 17:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。


1、 ...

赞这个图。。

gta

原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。


1、 ...

这个解法太巧妙了

shaohui

来一个与众不同的，是在其它地方看到的。

原来链表
->->-> x -> ->
       ^    |
       | <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点

同时链表呈

->->-> x <- <-
       |     |
       | -> -> y

显然，过程中可以统计出链表走过的节点数 L，不是环的部分走了2遍，也包括进去了
然后从起点走L/2步，走到那个中间节点，就是y，也是一边走一边反向
然后就是
<-<-<- x <- <- y'
       |     |
       | <- <- y

然后两个指针都从y和y'开始走，各走一步，交点就是x，环起点
至于要还原链表，从y'走向头，反向一次就好了

andyxie407

占个坑，留着用

emacsnw

原帖由 shaohui 于 2007-5-7 18:27 发表
来一个与众不同的，是在其它地方看到的。

原来链表
->->-> x -> ->
       ^    |
       | <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点

同时链表呈

->-& ...

这个是单向链表啊。

FireR2

最近似乎 总能看到 类似的题目，晕，难道面试管都上ChinaUnix？

thinkinnight

原帖由 shaohui 于 2007-5-8 10:27 发表
来一个与众不同的，是在其它地方看到的。

原来链表
->->-> x -> ->
       ^    |
       | <- <-
一边走，一边把链表反向
绕了一圈之后，最后会走回起点

同时链表呈

->-& ...

y和y' 不清楚说的是哪个点，一个是L/2的点，另一个呢？

shaohui

这个是单向链表啊。

注意每次遍历都会反转的

thinkinnight

链表反转的那个方法
b为奇数的时候是不是不行？

fertiland

http://ostermiller.org/find_loop_singly_linked_list.html