大四畢業(yè)前夕，計算機學(xué)院，

正在四處求職的小灰碰到了同系的學(xué)霸大黃......

小灰邊說邊回憶著上周去面試的情形......

有一個單向鏈表，鏈表當(dāng)中有可能出現(xiàn)“環(huán)”，就像下圖這樣。如何用程序判斷出這個鏈表是有環(huán)鏈表？

方法一：首先從頭節(jié)點開始，依次遍歷單鏈表的每一個節(jié)點。每遍歷到一個新節(jié)點，就從頭節(jié)點重新遍歷新節(jié)點之前的所有節(jié)點，用新節(jié)點ID和此節(jié)點之前所有節(jié)點ID依次作比較。如果發(fā)現(xiàn)新節(jié)點之前的所有節(jié)點當(dāng)中存在相同節(jié)點ID，則說明該節(jié)點被遍歷過兩次，鏈表有環(huán)；如果之前的所有節(jié)點當(dāng)中不存在相同的節(jié)點，就繼續(xù)遍歷下一個新節(jié)點，繼續(xù)重復(fù)剛才的操作。

例如這樣的鏈表：A->B->C->D->B->C->D， 當(dāng)遍歷到節(jié)點D的時候，我們需要比較的是之前的節(jié)點A、B、C，不存在相同節(jié)點。這時候要遍歷的下一個新節(jié)點是B，B之前的節(jié)點A、B、C、D中恰好也存在B，因此B出現(xiàn)了兩次，判斷出鏈表有環(huán)。

假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S。那么算法的時間復(fù)雜度是0+1+2+3+....+(D+S-1) = (D+S-1)*(D+S)/2 ， 可以簡單地理解成 O(N*N)。而此算法沒有創(chuàng)建額外存儲空間，空間復(fù)雜度可以簡單地理解成為O(1)。

方法二：首先創(chuàng)建一個以節(jié)點ID為鍵的HashSet集合，用來存儲曾經(jīng)遍歷過的節(jié)點。然后同樣是從頭節(jié)點開始，依次遍歷單鏈表的每一個節(jié)點。每遍歷到一個新節(jié)點，就用新節(jié)點和HashSet集合當(dāng)中存儲的節(jié)點作比較，如果發(fā)現(xiàn)HashSet當(dāng)中存在相同節(jié)點ID，則說明鏈表有環(huán)，如果HashSet當(dāng)中不存在相同的節(jié)點ID，就把這個新節(jié)點ID存入HashSet，之后進入下一節(jié)點，繼續(xù)重復(fù)剛才的操作。

這個方法在流程上和方法一類似，本質(zhì)的區(qū)別是使用了HashSet作為額外的緩存。

假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S。而每一次HashSet查找元素的時間復(fù)雜度是O(1), 所以總體的時間復(fù)雜度是1*(D+S)=D+S，可以簡單理解為O(N)。而算法的空間復(fù)雜度還是D+S-1，可以簡單地理解成O(N)。

等通知就是沒通知，這是職場上公認的語言。

以上就是小灰悲劇的回憶......

方法三：首先創(chuàng)建兩個指針1和2(在java里就是兩個對象引用)，同時指向這個鏈表的頭節(jié)點。然后開始一個大循環(huán)，在循環(huán)體中，讓指針1每次向下移動一個節(jié)點，讓指針2每次向下移動兩個節(jié)點，然后比較兩個指針指向的節(jié)點是否相同。如果相同，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)。

例如鏈表A->B->C->D->B->C->D，兩個指針最初都指向節(jié)點A，進入第一輪循環(huán)，指針1移動到了節(jié)點B，指針2移動到了C。第二輪循環(huán)，指針1移動到了節(jié)點C，指針2移動到了節(jié)點B。第三輪循環(huán)，指針1移動到了節(jié)點D，指針2移動到了節(jié)點D，此時兩指針指向同一節(jié)點，判斷出鏈表有環(huán)。

此方法也可以用一個更生動的例子來形容：在一個環(huán)形跑道上，兩個運動員在同一地點起跑，一個運動員速度快，一個運動員速度慢。當(dāng)兩人跑了一段時間，速度快的運動員必然會從速度慢的運動員身后再次追上并超過，原因很簡單，因為跑道是環(huán)形的。

假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S。那么循環(huán)會進行S次(為什么是S次，有心的同學(xué)可以自己揣摩下)，可以簡單理解為O(N)。除了兩個指針以外，沒有使用任何額外存儲空間，所以空間復(fù)雜度是O(1)。

問題一：判斷兩個單向鏈表是否相交，如果相交，求出交點。

問題二：在一個有環(huán)鏈表中，如何找出鏈表的入環(huán)點？

總結(jié)

以上是生活随笔為你收集整理的c++ 如何判断无效指针_如果链表中有环，我们应该如何判断？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。