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

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

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

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

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

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

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

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

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

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

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

在業(yè)界有一個(gè)經(jīng)典的算法，龜兔賽跑算法，主要用于檢測(cè)鏈表中是否存在環(huán)，通?？梢越鉀Q如下問題：

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

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

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

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

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

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

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

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

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

具體的解法如下：

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

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

代碼解讀如下：

代碼@1：只要當(dāng)前節(jié)點(diǎn)不為空，就可以繼續(xù)向后驅(qū)動(dòng)，主要是為了保證，在剛好擁有n個(gè)節(jié)點(diǎn)的情況下，能驅(qū)動(dòng)n次，也方便理解，例如現(xiàn)在有一個(gè)三個(gè)節(jié)點(diǎn)的鏈表，要?jiǎng)h除倒數(shù)第三個(gè)，其運(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)的題目，終極殺器：雙指針。

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