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

[adrianshum (Alien)]

※ 引述《pikahacker (喵)》之銘言：
: ※ [本文轉錄自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 標題: [請益] linked list裡如何找cycle?
: 時間: Mon Jan 25 13:06:55 2010
: 如果有人給妳一個linked list
: 有辦法在O(N)時間內,得知linked list中有沒有cycle?


初出來工作的時候, 有些老大出了這問題

當初沒有說用O(N) 的, 我想了一個麻煩的方法.
後來他說其實有一個 O(N) 的方法, 我再想一想
就想到了

其實比較像智力問題. 想自己想的話先不要往下看

防雷














兩支 ptr 指著 head, ptr A 每次往前移2格, ptr B 每次
移1格.

要是 ptr A reach 到 null 即是 non-cyclic
要是有一刻 ptr B 等如 A, 就是 cyclic

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 202.155.236.82
推 yauhh:水
推 yoco315:跟 rho method factorization 一樣耶 O_O
推 pikahacker:好美的解法
推 akasan:還是這個解法最優美
推 bobju:要證明是O(n)得用到數論.
推 cutecpu:推！
→ MOONRAKER:贊
推 lflin:如果 cycle number 是個質數...
→ lflin:                          喔 沒事 :p
推 DBoyX:好像賽車...