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

[bobju (寶貝豬)]

※ 引述《pikahacker (喵)》之銘言：
: ※ [本文轉錄自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 標題: [請益] linked list裡如何找cycle?
: 時間: Mon Jan 25 13:06:55 2010
: 如果有人給妳一個linked list
: 有辦法在O(N)時間內,得知linked list中有沒有cycle?
如果條件只是如此, 那應該很簡單吧?

只要在走訪過的node裏留下一個記號, 接著繼續走訪下一個node,

若在途中再次走訪到有記號的node, 就代表有cycle; 若直走到null

都沒再遇到有記號的node就代表沒cycle.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 58.115.151.184
→ adrianshum:這方法是 linked list 的 node 有地方
→ adrianshum:讓你放那個 flag 才行, 一般的 linked
→ adrianshum:list 不能當它有這種 field 吧...
→ bobju:但是問題裏並沒強調這點啊~所以我才語帶保留
→ bobju:如果這linked list的資料結構是我訂的,我當
→ bobju:然採用這種方法.
→ adrianshum:問題只說給你一條 linked list, 怎可以
→ adrianshum:當是自己定義的東西? 可以自訂, 我能做
→ adrianshum:到 O(1) 嘍... 只要在插入 node 的時候
→ adrianshum:做手腳就好了...
→ adrianshum:況且問題是 "有人給你一個linked list"
→ adrianshum:明顯就不是自己的東西了...
→ bobju:問題只給你一條linked list,但卻沒有限制說
→ bobju:不能複製或是寫入,這就是規則上的不明確.
→ bobju:我在走訪節點的同時,複製並寫入到另一條link
→ bobju:ed list, 並不會破壞原來的linked list,照樣
→ bobju:可依我的方法達到判斷的目的. 當然我知道你
→ bobju:的方法很smart, 只是除非有點演算法的功底,
→ bobju:否則臨場會解答只怕還得腦袋靈光不失常才行.
→ bobju:另外,要證明O(N)只怕功底就得更深厚了.
→ adrianshum:複制到另一 linked list 其實這就是我
→ adrianshum:第一次回答的做法 :P  不過在 "檢查"
→ adrianshum:這部份令到 complexity 變高 (O(N^2)?)
→ bobju:如果用陣列靜態複製,在檢查時就是O(N^2),但
→ bobju:是用動態複製就不會.