牛客網(wǎng)高頻算法題系列-BM6-判斷鏈表中是否有環(huán)

題目描述

判斷給定的鏈表中是否有環(huán)。如果有環(huán)則返回true，否則返回false。

原題目見：BM6 判斷鏈表中是否有環(huán)

解法一：雙指針法

使用兩個(gè)指針，fast 與 slow。它們起始都位于鏈表的頭部。隨后，slow 指針每次向后移動(dòng)一個(gè)位置，而fast 指針向后移動(dòng)兩個(gè)位置。如果鏈表中存在環(huán)，則 fast 指針最終將再次與 slow 指針在環(huán)中相遇。

原理可參考：雙指針?biāo)惴ㄔ碓斀?/span>

解法二：哈希法

使用HashSet記錄鏈表中的結(jié)點(diǎn)，然后遍歷鏈表結(jié)點(diǎn)：

• 如果鏈表中的結(jié)點(diǎn)在哈希表中出現(xiàn)過，說明鏈表有環(huán)，直接返回true

• 如果鏈表中的結(jié)點(diǎn)沒有在哈希表中出現(xiàn)過，則將當(dāng)前結(jié)點(diǎn)添加到哈希表中，然后判斷下一個(gè)結(jié)點(diǎn)

最后，如果沒有重復(fù)節(jié)點(diǎn)，則說明無環(huán)，返回false。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！