作者ddavid (謊言接線生)
看板Programming
標題Re: [請益] linked list裡如何找cycle?
時間Mon Jan 25 22:36:18 2010
※ 引述《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)
1F：→ yauhh:這也不對,所謂linked list就是應該有尾端 61.231.66.54 01/26 00:47
2F：→ yauhh:此外,也有有尾端並且中間夾帶圈圈的例子 61.231.66.54 01/26 00:48
3F：→ yauhh:至於尾端,有或沒有都有可能. 61.231.66.54 01/26 00:49
4F：→ xam:中間夾帶圈圈, 那就有節點犯規多指一個了 114.32.92.137 01/26 03:18
5F：推 nedbob:有cycle的linked list 你在掃的時候就會遇 140.135.11.175 01/26 04:43
6F：→ nedbob:到無窮迴圈 怎麼都停止不下來 140.135.11.175 01/26 04:43
7F：推 wupojung:如果next node有兩個 應該就變成graph 吧 140.128.86.18 01/26 10:34
8F：→ wupojung:linked list應該是 只有單向 雙向 Loop 140.128.86.18 01/26 10:35
9F：→ wupojung:當然loop 可以指回中間 就會變成2in 1out 140.128.86.18 01/26 10:35
10F：→ wupojung:當然發生在單向的時候...多個output 應該 140.128.86.18 01/26 10:36
11F：→ wupojung:不行..因為實作之前就要訂 struct了 140.128.86.18 01/26 10:37
12F：→ wupojung:如果無法預估ouput有幾個那 list 作不出 140.128.86.18 01/26 10:37
13F：→ wupojung:應該要寫成graph = =(or tree) 140.128.86.18 01/26 10:38
14F：→ adrianshum:原 po 你寫一個程式試一試就知道問題出 202.155.236.82 01/26 11:25
15F：→ adrianshum:在哪裡了. linked list 的 traverse 只 202.155.236.82 01/26 11:25
16F：→ adrianshum:能經由一個 node 的 next 到達另一個 202.155.236.82 01/26 11:26
17F：→ adrianshum:你一直 traverse, circular 的 linked 202.155.236.82 01/26 11:26
18F：→ adrianshum:list 會讓你一直都找到 next, 你要怎麼 202.155.236.82 01/26 11:26
19F：→ adrianshum:知道那是一直繞圈圈沒有null, 而不是還 202.155.236.82 01/26 11:27
20F：→ adrianshum:沒有到 null? 202.155.236.82 01/26 11:27
21F：推 AstralBrain:to樓上: 所以問題出在原po說的linked 220.133.186.66 01/26 12:02
22F：→ AstralBrain:list到底是指什麼東西 220.133.186.66 01/26 12:02
23F：→ AstralBrain:如果只是一般的有向圖 拿到所有vertex 220.133.186.66 01/26 12:02
24F：→ AstralBrain:是很合理的.. 220.133.186.66 01/26 12:02
25F：推 yauhh:喔,我了解了,我誤解本文的意思,的確檢查null 61.231.66.54 01/26 12:17
26F：→ yauhh:即可.不過一般所說"檢查所有node"是用走訪的 61.231.66.54 01/26 12:18
27F：→ yauhh:所以有adrianshum提的辦法.但如果是一般陣列 61.231.66.54 01/26 12:18
28F：→ yauhh:式的鏈接串列,做迴路檢查就很快了. 61.231.66.54 01/26 12:19
29F：→ ddavid:隔一天來看就爆出一堆推文XD 114.42.108.102 01/26 12:52
30F：→ ddavid:總之我只是要說特定情況下有個特殊解，不過 114.42.108.102 01/26 12:53
31F：→ ddavid:沒有講清楚是在拿到所有node（或知道個數） 114.42.108.102 01/26 12:53
32F：→ ddavid:的條件是我疏忽了XD 114.42.108.102 01/26 12:54