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

看板Programming作者adrianshum (Alien)時間14年前 (2010/01/25 14:44)推噓8(8推 0噓 2→)

留言10則, 9人參與討論串1/5 (看更多)

※ 引述《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

01/25 19:27, , 1^F

01/25 19:27, 1^F

推

yoco315

01/25 20:20, , 2^F

01/25 20:20, 2^F

推

pikahacker

01/25 22:21, , 3^F

01/25 22:21, 3^F