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

[nikeasyanzi (nikeasyanzi)]

想請問版上先進

    如果只是單純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
→ scwg:這邊討論的 singly linked list 是用走一步走兩步線性解的吧
→ scwg:對任意 non-weighted graph 用 bfs 或 dfs 都可以只是要額外
→ scwg:空間 (或時間), 用不到 Floyd-Warshall 啊..
推 singlovesong:linked list 不准有兩個next吧?
→ nikeasyanzi:回scwg大:沒錯 若任意的graph 用DFS BFS 是可以的
※ 編輯: nikeasyanzi     來自: 140.113.136.221      (10/08 14:35)
→ nikeasyanzi:回singal link list是有定義只有一個node沒錯
→ nikeasyanzi:只是小弟想詢問 萬一不是link list 怎麼辦
→ nikeasyanzi:因為floyd 似乎只適用在只有一個child 的graph上!!??
→ scwg:你看的是哪裡的 floyd o_O
推 guest2:我猜是指Tortoise and Hare Algorithm (floyd algo.)