?？途W(wǎng)高頻算法題系列-BM7-鏈表中環(huán)的入口結(jié)點(diǎn)

題目描述

給一個(gè)長(zhǎng)度為n鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，返回null。

原題目見(jiàn)：BM7 鏈表中環(huán)的入口結(jié)點(diǎn)

解法一：雙指針?lè)?/h1>

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

如果相遇了，從相遇處到入口結(jié)點(diǎn)的距離與頭結(jié)點(diǎn)與入口結(jié)點(diǎn)的距離相同。所以將fast重新設(shè)置為頭結(jié)點(diǎn)，fast和sow結(jié)點(diǎn)都一步步走，直到相遇，即為入口結(jié)點(diǎn)。

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

解法二：哈希法

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

• 如果鏈表中的結(jié)點(diǎn)在哈希表中出現(xiàn)過(guò)，說(shuō)明鏈表有環(huán)，并且該結(jié)點(diǎn)即為入口結(jié)點(diǎn)，返回之

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

最后，如果沒(méi)有重復(fù)節(jié)點(diǎn)，則說(shuō)明無(wú)環(huán)，返回null。

說(shuō)明：和 ?？途W(wǎng)高頻算法題系列-BM6-判斷鏈表中是否有環(huán) 的解法基本一致。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

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