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

[tiwei (∫期望dt=ivy + C)]

※ 引述《ddavid (謊言接線生)》之銘言：
: ※ 引述《adrianshum (Alien)》之銘言：
: : 初出來工作的時候, 有些老大出了這問題
: : 當初沒有說用O(N) 的, 我想了一個麻煩的方法.
: : 後來他說其實有一個 O(N) 的方法, 我再想一想
: : 就想到了
: : 其實比較像智力問題. 想自己想的話先不要往下看
: : 防雷
: : 兩支 ptr 指著 head, ptr A 每次往前移2格, ptr B 每次
: : 移1格.
這題是interview無敵常見題阿
印象中連Programming Interview Exposed這本書裡也有提到
Alien用的這個應該是標準解法
如果你google一下就會發現大家都用這個方法
: : 要是 ptr A reach 到 null 即是 non-cyclic
: : 要是有一刻 ptr B 等如 A, 就是 cyclic
:     話說，這個linked list是哪種linked list？
:     如果是單向、每個node只能指向一個其它node的話......
:     ......，那只要掃過一次所有node看看有沒有node指向null就好了，沒有就是有
這個方法就不行了..因為你怎麼知道你掃完所有node不是一直掃到重複的呢
前幾篇也有人提到把每個掃過得做標記
但這樣不就改了原本node的data..好像也不是個很好的做法
: cycle，因為此種linked list要是有迴圈就一定是最後一個點指回了前面某個點XD。
: 不會是分支造成的，因為沒法指向第二個點XD。時間上是O(N)，而且不需要額外的兩
: 個ptr，只需要一個bool flag XD
:     當然這只判定了有沒有，並沒找出那一圈是啥。不過內文寫「得知linked list
: 中有沒有cycle」，那麼這樣就可以了。
A->B->C
   ^
   |  |
   E<-D

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 160.39.43.40
→ ddavid:如上篇的推文，Linked list在拿到所有點的
→ ddavid:情況下才能用的特殊解這樣啦XD
推 Huangs:如果用 hash table 來存每個點是否拜訪過
→ Huangs:也是一種標記方式。hash table每次 check
→ Huangs:的平均複雜度是 O(1)，所以最後仍然是 O(N)
→ adrianshum:hash table 這招不錯耶... 我沒想到
推 ddavid:但在空間複雜度上輸了，因為至少要O(N)，而
→ ddavid:樓上你提的方法只要兩個額外ptr，是O(1)。
推 Huangs:linked list 就已經是 O(N)
→ Huangs:再多 O(N) 也還是 O(N)
→ Huangs:而且這題又沒有要求空間複雜度
推 ddavid:沒有要求但是我們可以最佳化啊XD
→ ddavid:標記法O(N)的係數小，但空間花得多，所以兩
→ ddavid:個方法依不同情況都會有用途。呃，不過實作
→ ddavid:上標記法是否真的係數較小就難說了XD