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

前文前文學習了基礎數據結構：鏈表(單鏈表)，接下來我將從leetcode中挑選幾道挺有意思的算法題，與大家一起來學習。

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

1、檢測一個單鏈表中是否存在環

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

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

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

代碼實現如下：

在算法領域通常有兩個維度來評估一款算法的優劣：時間復雜度、空間復雜度。

• 時間復雜度：O(N)，因為需要遍歷整個鏈表，隨著鏈表數據的增長，遍歷的次數就更多。
• 空間復雜度：O(N)，因為這里額外申請來一個空間用來存儲遍歷過的節點。

進階：能否對上述算法進行優化，將空間復雜度優化到O(1)。

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

• 檢測鏈表中是否存在環
• 如果存在環，計算出環的入口節點
• 如果存在環，計算出環的長度

從網上獲取“龜兔賽跑”的具體描述：

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

接下來我們可以根據這個規則，寫出示例代碼如下：

是不是非常優雅，只需要引入兩個指針。

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

2、刪除鏈表中倒數第n個節點

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

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

具體的解法如下：

引入兩個指針，初始狀態都執行Header節點，然后先讓一個指針移動n次，然后兩個指針同時移動，知道第一個指針到達鏈表的尾部，此時第二個指針就是倒數第n個節點，沿著上圖，當first移動到隊尾的狀態圖如下：

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

代碼解讀如下：

代碼@1：只要當前節點不為空，就可以繼續向后驅動，主要是為了保證，在剛好擁有n個節點的情況下，能驅動n次，也方便理解，例如現在有一個三個節點的鏈表，要刪除倒數第三個，其運行軌跡如下圖所示：

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

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

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

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

3、求鏈表的中間節點經過上面兩道題的講解與訓練，我相信讀者朋友們看到這種在鏈表領域與位置相關的題目，終極殺器：雙指針。

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