Re: [請益] linked list裡如何找cycle?
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間15年前 (2010/01/27 09:38)推噓4(4推 0噓 4→)留言8則, 4人參與討論串1/3 (看更多)
※ 引述《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
推
01/27 17:41, , 1F
01/27 17:41, 1F
推
01/27 17:44, , 2F
01/27 17:44, 2F
推
01/27 23:55, , 3F
01/27 23:55, 3F
→
01/28 09:23, , 4F
01/28 09:23, 4F
※ 編輯: FRAXIS 來自: 140.119.162.50 (01/28 09:50)
推
01/28 16:26, , 5F
01/28 16:26, 5F
→
01/28 16:27, , 6F
01/28 16:27, 6F
→
01/29 00:28, , 7F
01/29 00:28, 7F
→
01/29 00:29, , 8F
01/29 00:29, 8F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
