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

看板Programming作者tiwei (∫期望dt=ivy + C)時間14年前 (2010/01/26 12:39)推噓4(4推 0噓 11→)

留言15則, 3人參與討論串5/5 (看更多)

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

01/26 12:55, , 1^F

01/26 12:55, 1^F

→

ddavid

01/26 12:55, , 2^F

01/26 12:55, 2^F

推

Huangs

01/26 16:46, , 3^F

01/26 16:46, 3^F