作者FRAXIS (喔喔)
看板Prob_Solve
標題Re: [請益] linked list裡如何找cycle?
時間Wed Jan 27 09:38:43 2010
※ 引述《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)變數，陣列是唯讀。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推 Lucemia:想了一下果然都是cycle detect 的問題 01/27 17:41
推 Lucemia:另外不加這些條件的話用hash就很好解了 01/27 17:44
推 cplusplus:請問最後一題需要考慮重複個數>2和超過兩組值嗎?? 01/27 23:55
→ FRAXIS:哈 忘記加那個條件 應該只能有一組重複 01/28 09:23
※ 編輯: FRAXIS 來自: 140.119.162.50 (01/28 09:50)
推 cplusplus:那就很簡單了 :) 01/28 16:26
→ cplusplus:本來想了很久怎麼解決多組&多個...沒想到 01/28 16:27
→ yoco315:起點我想了好久 -_-" 今天有空就在想.. 01/29 00:28
→ yoco315:剛剛快睡著的時候終於想到了... XD 01/29 00:29