看板 [ Programming ]
討論串[請益] linked list裡如何找cycle?
共 5 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
Re: [請益] linked list裡如何找cycle?
推噓8(8推 0噓 2→)留言10則，0人參與, 最新作者adrianshum (Alien)時間14年前 (2010/01/25 14:44), 編輯資訊
1
0
0
內容預覽:
初出來工作的時候, 有些老大出了這問題. 當初沒有說用O(N) 的, 我想了一個麻煩的方法.. 後來他說其實有一個 O(N) 的方法, 我再想一想. 就想到了. 其實比較像智力問題. 想自己想的話先不要往下看. 防雷. 兩支 ptr 指著 head, ptr A 每次往前移2格, ptr B 每次.
#2
Re: [請益] linked list裡如何找cycle?
推噓0(0推 0噓 25→)留言25則，0人參與, 最新作者bobju (寶貝豬)時間14年前 (2010/01/25 21:19), 編輯資訊
0
0
0
內容預覽:
如果條件只是如此, 那應該很簡單吧?. 只要在走訪過的node裏留下一個記號, 接著繼續走訪下一個node,. 若在途中再次走訪到有記號的node, 就代表有cycle; 若直走到null. 都沒再遇到有記號的node就代表沒cycle.. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆
#3
Re: [請益] linked list裡如何找cycle?
推噓1(1推 0噓 3→)留言4則，0人參與, 最新作者StubbornLin (Victor)時間14年前 (2010/01/25 22:14), 編輯資訊
0
0
4
內容預覽:
如果你只是要知道是否有cycle. 用其它人的方法應該就可以. 我自己是有想到一個方法. 除了發現是否有cycle. 還可以用來找到所有cycle. 方法和想法很簡單. 就是本質上cycle的每個節點都有個特性. "都一定有別人指著它，而它也指著別人". 只要去掉不合這樣條件的節點. 重覆一直做，非
(還有177個字)
#4
Re: [請益] linked list裡如何找cycle?
推噓4(4推 0噓 28→)留言32則，0人參與, 最新作者ddavid (謊言接線生)時間14年前 (2010/01/25 22:36), 編輯資訊
1
0
0
內容預覽:
話說，這個linked list是哪種linked list？. 如果是單向、每個node只能指向一個其它node的話....... ......，那只要掃過一次所有node看看有沒有node指向null就好了，沒有就是有. cycle，因為此種linked list要是有迴圈就一定是最後一個點指回
(還有285個字)
#5
Re: [請益] linked list裡如何找cycle?
推噓4(4推 0噓 11→)留言15則，0人參與, 最新作者tiwei (∫期望dt=ivy + C)時間14年前 (2010/01/26 12:39), 編輯資訊
0
0
0
內容預覽:
這題是interview無敵常見題阿. 印象中連Programming Interview Exposed這本書裡也有提到. Alien用的這個應該是標準解法. 如果你google一下就會發現大家都用這個方法這個方法就不行了..因為你怎麼知道你掃完所有node不是一直掃到重複的呢前幾篇也有人提到把每
首頁
上一頁
1
下一頁
尾頁