作者tiwei (∫期望dt=ivy + C)
站內Programming
標題Re: [請益] linked list裡如何找cycle?
時間Tue Jan 26 12:39:11 2010
※ 引述《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
1F：→ ddavid:如上篇的推文，Linked list在拿到所有點的 114.42.108.102 01/26 12:55
2F：→ ddavid:情況下才能用的特殊解這樣啦XD 114.42.108.102 01/26 12:55
3F：推 Huangs:如果用 hash table 來存每個點是否拜訪過 61.217.25.93 01/26 16:46
4F：→ Huangs:也是一種標記方式。hash table每次 check 61.217.25.93 01/26 16:46
5F：→ Huangs:的平均複雜度是 O(1)，所以最後仍然是 O(N) 61.217.25.93 01/26 16:46
6F：→ adrianshum:hash table 這招不錯耶... 我沒想到 202.155.236.82 01/26 18:26
7F：推 ddavid:但在空間複雜度上輸了，因為至少要O(N)，而 114.36.142.187 01/26 21:41
8F：→ ddavid:樓上你提的方法只要兩個額外ptr，是O(1)。 114.36.142.187 01/26 21:41
9F：推 Huangs:linked list 就已經是 O(N) 61.217.25.93 01/28 13:25
10F：→ Huangs:再多 O(N) 也還是 O(N) 61.217.25.93 01/28 13:25
11F：→ Huangs:而且這題又沒有要求空間複雜度 61.217.25.93 01/28 13:25
12F：推 ddavid:沒有要求但是我們可以最佳化啊XD 114.36.137.168 01/28 19:54
13F：→ ddavid:標記法O(N)的係數小，但空間花得多，所以兩 114.36.137.168 01/28 19:55
14F：→ ddavid:個方法依不同情況都會有用途。呃，不過實作 114.36.137.168 01/28 19:57
15F：→ ddavid:上標記法是否真的係數較小就難說了XD 114.36.137.168 01/28 19:58