推 ddavid:除非這個linked list是雙向的，否則你的做 114.42.111.126 01/25 22:26
→ ddavid:法需要O(n^2)。 114.42.111.126 01/25 22:26
→ ddavid:因為要知道一個node有沒有被別人指，需要看 114.42.111.126 01/25 22:26
→ ddavid:過所有其它的node。 114.42.111.126 01/25 22:27
※ 引述《pikahacker (喵)》之銘言：
: ※ [本文轉錄自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 標題: [請益] linked list裡如何找cycle?
: 時間: Mon Jan 25 13:06:55 2010
: 如果有人給妳一個linked list
: 有辦法在O(N)時間內,得知linked list中有沒有cycle?
如果你只是要知道是否有cycle
用其它人的方法應該就可以
我自己是有想到一個方法
除了發現是否有cycle
還可以用來找到所有cycle
方法和想法很簡單
就是本質上cycle的每個節點都有個特性
"都一定有別人指著它，而它也指著別人"
只要去掉不合這樣條件的節點
重覆一直做，非cycle成員的的節點
起先會被除掉，這樣一來讓其它非cycle節點的成員
在接下來幾輪中，只要他不是cycle成員
鄰居又被去掉了，接著他們也會跟著不見
這樣一直去除，最後剩下的就全都是cycle的節點
就可以從中一個一個把他們挑出來
--
Now.in 網路廣播平台 http://now.in
哇咧咧 創意投票系統 http://walele.com
易記學 程式設計教學 http://ez2learn.com/
VICTOR's 個人Blog http://blog.ez2learn.com/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.70.149