前言

一個(gè)風(fēng)清月皎的夜晚，小萊獨(dú)自在操場漫步。突然一個(gè)熟悉的身影從旁邊經(jīng)過，小萊定睛一看，這不是心怡很久的女神嗎？小萊快走幾步追上女神后打了個(gè)招呼就徑直往前走了（沒出息）。為了加深女神對自己的印象，小萊決定再來一次偶遇（回頭是不可能回頭的）。只見小萊加快了步伐，終于再次偶遇到了自己的女神.....

本期主要分為以下幾個(gè)部分：

判斷是否有環(huán)

環(huán)的長度

環(huán)的入口

鏈表長度

畫外音：關(guān)于單鏈表知識，請點(diǎn)擊回顧。

判斷是否有環(huán)

如圖，這是一個(gè)鏈表存在環(huán)的示意圖。

我們?nèi)绾蝸砼袛嗍欠裼协h(huán)呢？小萊偶遇女神的例子或許對我們有所啟發(fā)。

在A點(diǎn)小萊和女神第一次相遇（起點(diǎn)）。

為了再次相遇，小萊在女神保持速度不變的情況下，采取了加(風(fēng))快(馳)步(電)伐(掣)的策略。由于操場是個(gè)環(huán)形，那么在兩個(gè)人一快一慢的場景下必然會再次相遇，于是在B點(diǎn)小萊又遇到了自己的女神。

畫外音：操場上想盡快遇到妹子，橫穿草坪超近道也是可以的哈！

那么結(jié)合到鏈表里如何處理呢？接下來我們的主角就該登場了：

「 快慢指針 」

在鏈表環(huán)的問題中我們常常用快慢指針來進(jìn)行處理，即設(shè)置slow、fast兩個(gè)指針變量（slow可以看作女神，fast可以看作小萊）：

slow每次走一步，即slow->next；

fast每次走兩步，即fast->next->next；

如果slow和fast相遇的話，即可以判斷當(dāng)前鏈表中有環(huán)。

代碼實(shí)現(xiàn)：

環(huán)的長度

既然知道了鏈表中有環(huán)，那么如何計(jì)算這個(gè)環(huán)的長度呢？

小萊和女神在B點(diǎn)相遇了，那么女神按照小萊的軌跡走一遍再回到B點(diǎn)，行走的路程不就是環(huán)的長度嗎？

畫外音：真他娘的聰明。

代碼實(shí)現(xiàn)：

p節(jié)點(diǎn)用來記錄B點(diǎn)的位置。

環(huán)的入口

如圖所示，現(xiàn)在我們想要知道環(huán)的入口位置。

假設(shè) A到C的距離為x，C到B的距離為y，環(huán)的長度為r。在B點(diǎn)相遇時(shí)，女神走的距離為s，那么小萊的距離則為2s（速度是女神的2倍）。

那么可以根據(jù)：

s = x + y;2s = x + y + n * r;

推導(dǎo)出：

x = n * r - y;

畫外音：n表示相遇時(shí)快指針（小萊）比慢指針（女神）多走的環(huán)數(shù)。

根據(jù)這個(gè)公式，我們可以設(shè)置兩個(gè)指針，一個(gè)在相遇點(diǎn)B，一個(gè)在起點(diǎn)A，然后兩個(gè)指針同時(shí)走（每次走一步），當(dāng)這兩個(gè)指針相遇時(shí)，此時(shí)的位置即為環(huán)的入口點(diǎn)。

鏈表長度

進(jìn)行到這里，鏈表長度的問題就簡單的多了。

根據(jù)前面兩步，我們知道了環(huán)的長度r，同時(shí)在獲取環(huán)的入口時(shí)可以計(jì)算出起始點(diǎn)到入口的距離x。那么鏈表的長度L就很容易得出來了。

鏈表長度L?=??起始點(diǎn)到入口的長度x +?環(huán)的長度y

我目前是在職前端開發(fā)，會前端，懂java，知Python，如果你現(xiàn)在也在學(xué)習(xí)前端，了解前端，渴望成為一名合格的前端開發(fā)工程師，在入門學(xué)習(xí)前端的過程當(dāng)中有遇見任何關(guān)于學(xué)習(xí)方法，學(xué)習(xí)路線，學(xué)習(xí)效率等方面的問題，你都可以申請加入我的前端學(xué)習(xí)交流群：518672693。里面聚集了一些正在自學(xué)前端的初學(xué)者，群文件里面還有我整理的一些不錯(cuò)的前端學(xué)習(xí)手冊，前端面試題，開發(fā)工具和PDF文檔書籍教程，需要的話都可以自行來獲取下載。