面向大象程式設計
本期例題：
- LeetCode 876 - Middle of the Linked List[1]（Easy）尋找連結清單中點
- LeetCode 19 - Remove Nth Node From End of List[2]（Medium）尋找連結清單的倒數第 k 個元素
- LeetCode 141 - Linked List Cycle[3]（Easy）判斷連結清單中是否存在環
上一篇文章中，我們分析了經典的 Two Sum II 問題與雙指針方法。雙指針這個名字在很多題解中都能見到，那麼，還有什麼題目可以用雙指針方法解決呢？
實際上，雙指針是一個很籠統的概念。隻要在解題時用到了兩個指針（連結清單指針、數組下标皆可），都可以叫做雙指針方法。根據兩個指針運動方式的不同，雙指針方法可以分成同向指針、對向指針、快慢指針等。
當雙指針方法遇到連結清單問題，我們主要使用快慢指針方法。很多時候連結清單操作遇到疑難雜症時，可以使用快慢指針，減少算法所需的時間或者空間。
這篇文章将會包含：
- 連結清單問題中的快慢指針特點
- 快慢指針的案例講解：尋找連結清單中點、尋找連結清單的倒數第 k 個元素
- 快慢指針的經典例題：判斷連結清單中是否存在環
- 相關題目
連結清單問題中的雙指針
我們知道，連結清單資料類型的特點決定了它隻能單向順序通路，而不能逆向周遊或随機通路（按下标通路）。很多時候，我們需要使用快慢指針的技巧來實作一定程式的逆向周遊，或者減少周遊的次數。這就是為什麼快慢指針常用于連結清單問題。
連結清單問題中的快慢指針又可以細分為多個不同類型。下面将依次介紹快慢指針的三個應用場景。
例題 1：尋找連結清單中點
LeetCode 876 - Middle of the Linked List[4]（Easy）
尋找連結清單中點的正常做法是，先周遊一遍連結清單，計算連結清單的長度
。再周遊一遍連結清單，找到第
更巧妙的做法是使用一快一慢兩個指針。快指針一次前進兩個結點，速度是慢指針的兩倍。這樣當快指針到達連結清單尾部時，慢指針正好到達的連結清單的中部。過程如下方動圖所示。這樣隻需周遊連結清單一遍。當然，時間複雜度仍然是
，不過連結清單類題目就是需要這樣減少一次周遊的技巧。
快慢指針不同速度前進（動圖）
題解代碼如下所示。注意循環的條件是
fast != null && fast.next != null
，防止出現空指針異常。
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
// fast 一次前進兩個元素，slow 一次前進一個元素
fast = fast.next.next;
slow = slow.next;
}
// 連結清單元素為奇數個時，slow 指向連結清單的中點
// 連結清單元素為偶數個時，slow 指向連結清單兩個中點的右邊一個
return slow;
} 例題 2：尋找連結清單的倒數第 k 個元素
LeetCode 19 - Remove Nth Node From End of List[5]（Medium）
尋找連結清單的倒數第
個元素的正常做法是，先周遊一遍連結清單，計算連結清單的長度
。這樣就可以計算出要找第
這裡同樣可以使用快慢指針方法減少一次周遊。不過這次兩個指針速度相同，隻是間隔一定距離。快指針先前進
個元素，然後兩個指針同樣速度前進。這樣當快指針到達連結清單尾部時，慢指針正好到達連結清單的倒數第
個元素。下面的動圖展示了快慢指針的前進過程（以
快慢指針間隔 3 個元素前進（動圖）
題解代碼如下所示。注意例題中除了尋找倒數第 k 個元素，還需要删除它。為了删除元素，我們需要用到第一講中所講的連結清單周遊架構，将
slow
指針變成
prev
和
curr
兩個指針。（關于
prev
和
curr
指針的具體用法，請自行回顧第一講。）是以這裡實際上是三個指針一起前進，注意分辨指針之間的關系。
public ListNode removeNthFromEnd(ListNode head, int k) {
// 将 fast 前進 k 個元素
ListNode fast = head;
for (int i = 0; i < k; i++) {
// 這裡省略了檢測空指針的代碼
fast = fast.next;
}
// fast 和 slow 指針間隔 k 個同時前進
// 這裡使用了連結清單周遊架構，将 slow 指針變成兩個指針 curr 和 prev
ListNode curr = head;
ListNode prev = null;
while (fast != null) {
prev = curr;
curr = curr.next;
fast = fast.next;
}
if (prev == null) {
head = curr.next;
} else {
prev.next = curr.next;
}
return head;
} 這裡題目假設了 k 的取值一定是合法的，是以代碼中省略了若幹合法性檢查。但是在面試中，我們應該考慮輸入
例題 3：判斷連結清單中是否存在環
LeetCode 141 - Linked List Cycle[6]（Easy）
這道題的連結清單進行了小小的變種。連結清單的尾結點有可能指向連結清單中的某個結點，讓連結清單成為環形，如下圖所示。
連結清單中的環
我們需要判斷連結清單是普通連結清單還是帶環的連結清單。如果隻使用一個指針周遊的話，其實是很難判斷是環的存在的，隻能用一個 set 儲存周遊過的所有結點。而如果使用快慢指針的話，則可以不使用額外空間。
我們讓快指針一次前進兩個結點，慢指針一次前進一個結點。當快慢指針都進入環路時，快指針會将慢指針“套圈”，從後面追上慢指針。追及的過程如下面的動圖所示。
快慢指針不同速度前進并追及（動圖）
而如果連結清單中不存在環的話，快指針則不會和慢指針指向同一個結點，而是會走到連結清單結尾。依照這個思路我們可以得到以下的題解代碼。
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// fast 和 slow 指向同一個結點，說明存在“套圈”
if (fast == slow) {
return true;
}
}
// fast 到達連結清單尾部，則不存在環
return false;
} 這一題還有第二問，LeetCode 142 - Linked List Cycle II[7]，找到連結清單入環的第一個結點。這也需要用到快慢指針，還涉及到一些證明。這一題本文就不展開講了，有興趣的同學可以自己嘗試解決此題。
總結
本文講解的是雙指針技巧中的一類“快慢指針”，用于解決連結清單類問題。而快慢指針又存在着多個變種，文中也一一列舉了。
連結清單類題目并不複雜，本系列第一講的連結清單周遊架構和本文所講的快慢指針就是連結清單類問題中最主要的兩個技巧了。連結清單類問題隻要多加練習，都非常的容易。
最後，附上一道連結清單問題的綜合練習題：連結清單排序（LeetCode 148 - Sort List[8]）。這道題中需要使用到連結清單處理的各種技巧，還需要針對連結清單的性質選擇合适的排序方法。可以說隻要掌握了這道題，就算掌握了連結清單類問題了。連結清單排序也是微軟面試中某個面試官的“三闆斧”之一，可以看出這道題的普适性。
上一講和這一講我們分别了解了兩種不同類型的雙指針方法：對向指針和快慢指針。雙指針還有一種經典的類型是滑動視窗，将在後面的章節進行講解。敬請期待。
參考資料
[1]
LeetCode 876 - Middle of the Linked List: https://leetcode.com/problems/middle-of-the-linked-list/
[2]
LeetCode 19 - Remove Nth Node From End of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
[3]
LeetCode 141 - Linked List Cycle: https://leetcode.com/problems/linked-list-cycle/
[4]
LeetCode 876 - Middle of the Linked List: https://leetcode.com/problems/middle-of-the-linked-list/
[5]
LeetCode 19 - Remove Nth Node From End of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
[6]
LeetCode 141 - Linked List Cycle: https://leetcode.com/problems/linked-list-cycle/
[7]
LeetCode 142 - Linked List Cycle II: https://leetcode.com/problems/linked-list-cycle-ii/
[8]
LeetCode 148 - Sort List: https://leetcode.com/problems/sort-list/
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下