java實作單鍊錶中是否有環的方法詳解
這是一道微軟經典筆試題,就是兩個指針h1,h2都從頭開始遍歷單鍊錶,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,表示環不存在;如果h2碰到本來應該在身後的h1說明環存在(也就是發生了套圈)。如果環不存在,一定是h2先碰到NULL:如果環存在,h2與h1一定會相遇,而且相遇的點在環內:h2比h1遍歷的速度快,一定不會在開始的那段非環的鍊錶部分相遇,所以當h1,h2都進入環後,h2每次移動都會使h2與h1之間在前進方向上的差距縮小1,最後,會使得h1和h2差距減少為0,也即相遇複製程式碼如
2024-11-24