Re: [請益] linked list裡如何找cycle?
※ 引述《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
推
01/25 22:26, , 1F
01/25 22:26, 1F
→
01/25 22:26, , 2F
01/25 22:26, 2F
→
01/25 22:26, , 3F
01/25 22:26, 3F
→
01/25 22:27, , 4F
01/25 22:27, 4F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 5 篇)：