Re: [請益] linked list裡如何找cycle?
看板Prob_Solve (計算數學 Problem Solving)作者nikeasyanzi (nikeasyanzi)時間11年前 (2013/10/07 22:19)推噓2(2推 0噓 8→)留言10則, 4人參與討論串2/3 (看更多)
想請問版上先進
如果只是單純singal linking list
那可以用floyd's algorithm 即可解
但萬一是任意node 允許連到兩個以上相異點 類似m-way tree
parent 可能不只有一個child
用floyd's algorithm不就解不了?
只能用kruskal algorithm 一個個edge加入來檢查cycle這樣 是嬤?
還是有其他更好的演算法??
懇請賜教!
※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《pikahacker (喵)》之銘言：
: : 如果有人給妳一個linked list
: : 有辦法在O(N)時間內,得知linked list中有沒有cycle?
: 這種題目算是面試常見題吧..
: 有時候除了要判斷有沒有cycle，還會問cycle起點在哪？
: 這種問題都會要求O(n)時間O(1)變數，且串列是唯讀的。
: 還有一個變型，給定兩條單向鍊結串列L和L'，但是L和L'可能在中途會
: 指向同一個節點，然後就重合到串列的尾巴（因為是單向的）。
: 要怎麼判斷有無重合？重合的起點在哪？ 要求O(n)的時間和O(1)變數。
: 另外也有一個相關問題
: 給定一個長度為n+1的陣列 a1 ... an+1，1 <= ak <= n for all k
: 除了一對ai=aj之外，其他ak的值都是相異的
: ai是多少？i和j是多少？ 只能使用O(n)的時間和O(1)變數，陣列是唯讀。
--
CyberPanel 5000CP 換 NT.500
http://myurl.com.tw/05bd
EmailCash 5000e 換 NT.500
http://myurl.com.tw/rgdq
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.199.98
→
10/08 00:06, , 1F
10/08 00:06, 1F
→
10/08 00:09, , 2F
10/08 00:09, 2F
→
10/08 00:09, , 3F
10/08 00:09, 3F
推
10/08 08:57, , 4F
10/08 08:57, 4F
→
10/08 14:34, , 5F
10/08 14:34, 5F
※ 編輯: nikeasyanzi 來自: 140.113.136.221 (10/08 14:35)
→
10/08 14:36, , 6F
10/08 14:36, 6F
→
10/08 14:37, , 7F
10/08 14:37, 7F
→
10/08 14:39, , 8F
10/08 14:39, 8F
→
10/08 20:35, , 9F
10/08 20:35, 9F
推
10/08 23:32, , 10F
10/08 23:32, 10F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
