作者bobju (寶貝豬)
看板Programming
標題Re: [請益] linked list裡如何找cycle?
時間Mon Jan 25 21:18:57 2010
※ 引述《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
1F：→ adrianshum:這方法是 linked list 的 node 有地方 202.155.236.82 01/26 14:40
2F：→ adrianshum:讓你放那個 flag 才行, 一般的 linked 202.155.236.82 01/26 14:40
3F：→ adrianshum:list 不能當它有這種 field 吧... 202.155.236.82 01/26 14:41
4F：→ bobju:但是問題裏並沒強調這點啊~所以我才語帶保留 58.115.151.184 01/26 14:50
5F：→ bobju:如果這linked list的資料結構是我訂的,我當 58.115.151.184 01/26 14:50
6F：→ bobju:然採用這種方法. 58.115.151.184 01/26 14:51
7F：→ adrianshum:問題只說給你一條 linked list, 怎可以 202.155.236.82 01/26 16:03
8F：→ adrianshum:當是自己定義的東西? 可以自訂, 我能做 202.155.236.82 01/26 16:04
9F：→ adrianshum:到 O(1) 嘍... 只要在插入 node 的時候 202.155.236.82 01/26 16:04
10F：→ adrianshum:做手腳就好了... 202.155.236.82 01/26 16:04
11F：→ adrianshum:況且問題是 "有人給你一個linked list" 202.155.236.82 01/26 16:05
12F：→ adrianshum:明顯就不是自己的東西了... 202.155.236.82 01/26 16:05
13F：→ bobju:問題只給你一條linked list,但卻沒有限制說 58.115.151.184 01/26 18:00
14F：→ bobju:不能複製或是寫入,這就是規則上的不明確. 58.115.151.184 01/26 18:00
15F：→ bobju:我在走訪節點的同時,複製並寫入到另一條link 58.115.151.184 01/26 18:01
16F：→ bobju:ed list, 並不會破壞原來的linked list,照樣 58.115.151.184 01/26 18:01
17F：→ bobju:可依我的方法達到判斷的目的. 當然我知道你 58.115.151.184 01/26 18:02
18F：→ bobju:的方法很smart, 只是除非有點演算法的功底, 58.115.151.184 01/26 18:02
19F：→ bobju:否則臨場會解答只怕還得腦袋靈光不失常才行. 58.115.151.184 01/26 18:02
20F：→ bobju:另外,要證明O(N)只怕功底就得更深厚了. 58.115.151.184 01/26 18:03
21F：→ adrianshum:複制到另一 linked list 其實這就是我 202.155.236.82 01/26 18:23
22F：→ adrianshum:第一次回答的做法 :P 不過在 "檢查" 202.155.236.82 01/26 18:23
23F：→ adrianshum:這部份令到 complexity 變高 (O(N^2)?) 202.155.236.82 01/26 18:24
24F：→ bobju:如果用陣列靜態複製,在檢查時就是O(N^2),但 58.115.151.184 01/29 14:18
25F：→ bobju:是用動態複製就不會. 58.115.151.184 01/29 14:18