我現(xiàn)在有點(diǎn)明白了，在面試過程中面試官有時會讓我們手寫代碼，其實(shí)主要是考驗(yàn)大家的基本功，更是通過大眾都熟悉的領(lǐng)域來考核大家的體系化思維與應(yīng)對思路。

前文前文學(xué)習(xí)了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：鏈表(單鏈表)，接下來我將從leetcode中挑選幾道挺有意思的算法題，與大家一起來學(xué)習(xí)。

鏈表中如果與相對位置有關(guān)的，基本通過引入雙指針(快慢指針)即可實(shí)現(xiàn)一次遍歷就求解。

1、檢測一個單鏈表中是否存在環(huán)

題目：如果給你一個指定的單鏈表，請判斷是否存在環(huán)。

作為一個算法小白來說，看到這個題目，不假思索后想到的思路一定是：引入一個HashSet，然后從頭開始遍歷單鏈表，將每一個元素存儲到HashSet中，在遍歷過程中，如果該元素在節(jié)點(diǎn)在HashSet中存在，則表示存儲環(huán)。

溫馨提示：本文的鏈表使用上文筆者手寫的鏈表。

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

在算法領(lǐng)域通常有兩個維度來評估一款算法的優(yōu)劣：時間復(fù)雜度、空間復(fù)雜度。

• 時間復(fù)雜度：O(N)，因?yàn)樾枰闅v整個鏈表，隨著鏈表數(shù)據(jù)的增長，遍歷的次數(shù)就更多。
• 空間復(fù)雜度：O(N)，因?yàn)檫@里額外申請來一個空間用來存儲遍歷過的節(jié)點(diǎn)。

進(jìn)階：能否對上述算法進(jìn)行優(yōu)化，將空間復(fù)雜度優(yōu)化到O(1)。

在業(yè)界有一個經(jīng)典的算法，龜兔賽跑算法，主要用于檢測鏈表中是否存在環(huán)，通常可以解決如下問題：

• 檢測鏈表中是否存在環(huán)
• 如果存在環(huán)，計算出環(huán)的入口節(jié)點(diǎn)
• 如果存在環(huán)，計算出環(huán)的長度

從網(wǎng)上獲取“龜兔賽跑”的具體描述：

龜兔賽跑算法的理論一：引入兩個快慢兩個指針，兩個指針同時從鏈表的頭節(jié)點(diǎn)開始遍歷，快指針每次移動2，慢指針每次移動1步，如果鏈表存儲環(huán)，快指針最終會追上慢指針，即兩個指針會重合;

接下來我們可以根據(jù)這個規(guī)則，寫出示例代碼如下：

是不是非常優(yōu)雅，只需要引入兩個指針。

龜兔賽跑算法的理論二：快慢指針在第一次相遇后，如果要求環(huán)的入口，方法為：將slow指針移動到隊(duì)列頭部，然后快慢指針第一次相遇的點(diǎn)，即為環(huán)的入口節(jié)點(diǎn)。

2、刪除鏈表中倒數(shù)第n個節(jié)點(diǎn)

在沒有了解到“龜兔賽跑算法”之前，要刪除倒數(shù)第n個節(jié)點(diǎn)，大家肯定會先遍歷一次鏈表，得出鏈表的總長度用len表示，然后再次遍歷，第二次遍歷只需遍歷的次數(shù)為(len-n)個節(jié)點(diǎn)即可。

但我們學(xué)習(xí)了龜兔賽跑算法之后，我相信讀者朋友們一定也能夠想到，引入兩個指針，可以只需要遍歷一次。

具體的解法如下：

引入兩個指針，初始狀態(tài)都執(zhí)行Header節(jié)點(diǎn)，然后先讓一個指針移動n次，然后兩個指針同時移動，知道第一個指針到達(dá)鏈表的尾部，此時第二個指針就是倒數(shù)第n個節(jié)點(diǎn)，沿著上圖，當(dāng)first移動到隊(duì)尾的狀態(tài)圖如下：

與具體寫代碼有關(guān)，最終如上圖所示，由于是刪除倒數(shù)第n個節(jié)點(diǎn)，并且是單鏈表，故通常需要先找到要刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，從這方面考慮，上述結(jié)束條件選用第一種比較合適，接下來是根據(jù)上述思路的代碼實(shí)現(xiàn)：

代碼解讀如下：

代碼@1：只要當(dāng)前節(jié)點(diǎn)不為空，就可以繼續(xù)向后驅(qū)動，主要是為了保證，在剛好擁有n個節(jié)點(diǎn)的情況下，能驅(qū)動n次，也方便理解，例如現(xiàn)在有一個三個節(jié)點(diǎn)的鏈表，要刪除倒數(shù)第三個，其運(yùn)行軌跡如下圖所示：

代碼@2：如果i小于n，說明沒有遍歷n次，缺少元素，直接拋出數(shù)組越界異常。

代碼@3：說明剛好遍歷了n次，正如上圖所示，則直接刪除頭節(jié)點(diǎn)。

代碼@4：接下來將同步推進(jìn)first，second指針，由于單鏈表刪除節(jié)點(diǎn)，需要知道被刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，故first指針指向尾節(jié)點(diǎn)(node.next == null，表示到達(dá)尾部)，如下圖所示：

代碼的解讀就到這里了，不得不佩服雙指針的強(qiáng)大之處。

3、求鏈表的中間節(jié)點(diǎn)經(jīng)過上面兩道題的講解與訓(xùn)練，我相信讀者朋友們看到這種在鏈表領(lǐng)域與位置相關(guān)的題目，終極殺器：雙指針。

解題方法：中間位置，那我們可以引入快慢兩個指針，快指針是慢指針的2倍速率，這樣當(dāng)快指針到達(dá)鏈表尾部，慢指針就正好走在鏈表的中間件位置。