PTT數位生活區 / Programming

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

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