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

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