Re: [請益] linked list裡如何找cycle?

[ddavid (謊言接線生)]

※ 引述《adrianshum (Alien)》之銘言：
: ※ 引述《pikahacker (喵)》之銘言：
: : 作者: pikahacker (喵) 看板: Prob_Solve
: : 標題: [請益] linked list裡如何找cycle?
: : 時間: Mon Jan 25 13:06:55 2010
: : 如果有人給妳一個linked list
: : 有辦法在O(N)時間內,得知linked list中有沒有cycle?
: 初出來工作的時候, 有些老大出了這問題
: 當初沒有說用O(N) 的, 我想了一個麻煩的方法.
: 後來他說其實有一個 O(N) 的方法, 我再想一想
: 就想到了
: 其實比較像智力問題. 想自己想的話先不要往下看
: 防雷
: 兩支 ptr 指著 head, ptr A 每次往前移2格, ptr B 每次
: 移1格.
: 要是 ptr A reach 到 null 即是 non-cyclic
: 要是有一刻 ptr B 等如 A, 就是 cyclic
    話說，這個linked list是哪種linked list？

    如果是單向、每個node只能指向一個其它node的話......

    ......，那只要掃過一次所有node看看有沒有node指向null就好了，沒有就是有
cycle，因為此種linked list要是有迴圈就一定是最後一個點指回了前面某個點XD。
不會是分支造成的，因為沒法指向第二個點XD。時間上是O(N)，而且不需要額外的兩
個ptr，只需要一個bool flag XD

    當然這只判定了有沒有，並沒找出那一圈是啥。不過內文寫「得知linked list
中有沒有cycle」，那麼這樣就可以了。

--
    「你會死。」不由分說，他被狠狠罵了一頓。

    午休時，我拉著他到安靜的地方。「你怎麼對著人這樣說話呢？」

    「他本來就會死，難道他不會死？」他抱怨。
                                                      －－預言師

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: ddavid          來自: 114.42.111.126       (01/25 22:41)
※ 編輯: ddavid          來自: 114.42.111.126       (01/25 22:43)
→ yauhh:這也不對,所謂linked list就是應該有尾端
→ yauhh:此外,也有有尾端並且中間夾帶圈圈的例子
→ yauhh:至於尾端,有或沒有都有可能.
→ xam:中間夾帶圈圈, 那就有節點犯規多指一個了
推 nedbob:有cycle的linked list 你在掃的時候就會遇
→ nedbob:到無窮迴圈  怎麼都停止不下來
推 wupojung:如果next node有兩個 應該就變成graph 吧
→ wupojung:linked  list應該是 只有單向 雙向 Loop
→ wupojung:當然loop 可以指回中間 就會變成2in 1out
→ wupojung:當然發生在單向的時候...多個output 應該
→ wupojung:不行..因為實作之前就要訂 struct了
→ wupojung:如果無法預估ouput有幾個那 list 作不出
→ wupojung:應該要寫成graph = =(or tree)
→ adrianshum:原 po 你寫一個程式試一試就知道問題出
→ adrianshum:在哪裡了. linked list 的 traverse 只
→ adrianshum:能經由一個 node 的 next 到達另一個
→ adrianshum:你一直 traverse, circular 的 linked
→ adrianshum:list 會讓你一直都找到 next, 你要怎麼
→ adrianshum:知道那是一直繞圈圈沒有null, 而不是還
→ adrianshum:沒有到 null?
推 AstralBrain:to樓上: 所以問題出在原po說的linked
→ AstralBrain:list到底是指什麼東西
→ AstralBrain:如果只是一般的有向圖 拿到所有vertex
→ AstralBrain:是很合理的..
推 yauhh:喔,我了解了,我誤解本文的意思,的確檢查null
→ yauhh:即可.不過一般所說"檢查所有node"是用走訪的
→ yauhh:所以有adrianshum提的辦法.但如果是一般陣列
→ yauhh:式的鏈接串列,做迴路檢查就很快了.
→ ddavid:隔一天來看就爆出一堆推文XD
→ ddavid:總之我只是要說特定情況下有個特殊解，不過
→ ddavid:沒有講清楚是在拿到所有node（或知道個數）
→ ddavid:的條件是我疏忽了XD