一個關(guān)于單向鏈表的面試題。

emacsnw

原帖由 win_hate 于 2007-4-29 17:51 發(fā)表
這個帖子這么長了。看了后面的回復(fù)，覺得很多朋友沒有理解 Emacsnw 的方法。其實他的方法已經(jīng)很簡明了，相比之下我給出的解答則比較艱澀隱晦�，F(xiàn)在把我的方法解釋一次，順帶也把 emacsnw 的方法說一下。


1、 ...

贊這個圖。。

gta

原帖由 win_hate 于 2007-4-30 09:51 發(fā)表
這個帖子這么長了。看了后面的回復(fù)，覺得很多朋友沒有理解 Emacsnw 的方法。其實他的方法已經(jīng)很簡明了，相比之下我給出的解答則比較艱澀隱晦�，F(xiàn)在把我的方法解釋一次，順帶也把 emacsnw 的方法說一下。


1、 ...

這個解法太巧妙了

shaohui

來一個與眾不同的，是在其它地方看到的。

原來鏈表
->->-> x -> ->
       ^    |
       | <- <-
一邊走，一邊把鏈表反向
繞了一圈之后，最后會走回起點

同時鏈表呈

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

顯然，過程中可以統(tǒng)計出鏈表走過的節(jié)點數(shù) L，不是環(huán)的部分走了2遍，也包括進(jìn)去了
然后從起點走L/2步，走到那個中間節(jié)點，就是y，也是一邊走一邊反向
然后就是
<-<-<- x <- <- y'
       |     |
       | <- <- y

然后兩個指針都從y和y'開始走，各走一步，交點就是x，環(huán)起點
至于要還原鏈表，從y'走向頭，反向一次就好了

andyxie407

占個坑，留著用

emacsnw

原帖由 shaohui 于 2007-5-7 18:27 發(fā)表
來一個與眾不同的，是在其它地方看到的。

原來鏈表
->->-> x -> ->
       ^    |
       | <- <-
一邊走，一邊把鏈表反向
繞了一圈之后，最后會走回起點

同時鏈表呈

->-& ...

這個是單向鏈表啊。

FireR2

最近似乎 總能看到 類似的題目，暈，難道面試管都上ChinaUnix？

thinkinnight

原帖由 shaohui 于 2007-5-8 10:27 發(fā)表
來一個與眾不同的，是在其它地方看到的。

原來鏈表
->->-> x -> ->
       ^    |
       | <- <-
一邊走，一邊把鏈表反向
繞了一圈之后，最后會走回起點

同時鏈表呈

->-& ...

y和y' 不清楚說的是哪個點，一個是L/2的點，另一個呢？

shaohui

這個是單向鏈表啊。

注意每次遍歷都會反轉(zhuǎn)的

thinkinnight

鏈表反轉(zhuǎn)的那個方法
b為奇數(shù)的時候是不是不行？

fertiland

http://ostermiller.org/find_loop_singly_linked_list.html