06.29 「算法」如何判斷鏈表有環

點擊上方"java全棧技術"關注，每天學習一個java知識點

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

有一個單向鏈表，鏈表當中有可能出現“環”，就像下圖這樣。如何用程序判斷出這個鏈表是有環鏈表？

方法一：首先從頭節點開始，依次遍歷單鏈表的每一個節點。每遍歷到一個新節點，就從頭節點重新遍歷新節點之前的所有節點，用新節點ID和此節點之前所有節點ID依次作比較。如果發現新節點之前的所有節點當中存在相同節點ID，則說明該節點被遍歷過兩次，鏈表有環；如果之前的所有節點當中不存在相同的節點，就繼續遍歷下一個新節點，繼續重複剛才的操作。

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

假設從鏈表頭節點到入環點的距離是D，鏈表的環長是S。那麼算法的時間複雜度是0+1+2+3+....+(D+S-1) = (D+S-1)*(D+S)/2 ， 可以簡單地理解成 O(N*N)。而此算法沒有創建額外存儲空間，空間複雜度可以簡單地理解成為O(1)。

方法二：首先創建一個以節點ID為鍵的HashSet集合，用來存儲曾經遍歷過的節點。然後同樣是從頭節點開始，依次遍歷單鏈表的每一個節點。每遍歷到一個新節點，就用新節點和HashSet集合當中存儲的節點作比較，如果發現HashSet當中存在相同節點ID，則說明鏈表有環，如果HashSet當中不存在相同的節點ID，就把這個新節點ID存入HashSet，之後進入下一節點，繼續重複剛才的操作。

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

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

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

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

方法三：首先創建兩個指針1和2（在java裡就是兩個對象引用），同時指向這個鏈表的頭節點。然後開始一個大循環，在循環體中，讓指針1每次向下移動一個節點，讓指針2每次向下移動兩個節點，然後比較兩個指針指向的節點是否相同。如果相同，則判斷出鏈表有環，如果不同，則繼續下一次循環。

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

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

假設從鏈表頭節點到入環點的距離是D，鏈表的環長是S。那麼循環會進行S次（為什麼是S次，有心的同學可以自己揣摩下），可以簡單理解為O（N）。除了兩個指針以外，沒有使用任何額外存儲空間，所以空間複雜度是O（1）。

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

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

文章轉自程序員小灰