作者 | 碼海
前言
這一篇我們來看看連結清單的另一個解題技巧：快慢指針。
快慢指針在面試中出現的機率也很大，也是務必要掌握的一個要點，本文總結了市面上常見的快慢指針解題技巧，相信看完後此類問題能手到擒來。本文将詳細講述如何用快慢指針解決以下兩大類問題
- 尋找/删除第 K 個結點
- 有關連結清單環問題的相關解法
尋找/删除第 K 個結點
小試牛刀之一
LeetCode 876：給定一個帶有頭結點 head 的非空單連結清單，傳回連結清單的中間結點。如果有兩個中間結點，則傳回第二個中間結點。
解法一
要知道連結清單的中間結點，首先我們需要知道連結清單的長度，說到連結清單長度大家想到了啥，還記得我們在上文中說過哨兵結點可以儲存連結清單的長度嗎，這樣直接 從 head 的後繼結點 開始周遊 連結清單長度 / 2 次即可找到中間結點。為啥中間結點是 連結清單長度/2，我們仔細分析一下
- 假如連結清單長度是奇數: head--->1--->2--->3--->4--->5, 從 1 開始周遊 5/2 = 2 （取整）次，到達 3，3确實是中間結點
- 假如連結清單長度是偶數: head--->1--->2--->3--->4--->5--->6, 從 1 開始周遊 6/2 = 3次，到達 4，4 确實是中間結點的第二個結點
畫外音：多畫畫圖，舉舉例，能看清事情的本質！
哨後結點的長度派上用場了，這種方式最簡單，直接上代碼
public Node findMiddleNode() {
Node tmp = head.next;
int middleLength = length / 2;
while (middleLength > 0) {
tmp = tmp.next;
middleLength--;
}
return tmp;
} 解法二
如果哨兵結點裡沒有定義長度呢，那就要周遊一遍連結清單拿到連結清單長度（定義為 length）了，然後再從頭結點開始周遊 length / 2 次即為中間結點
public Node findMiddleNodeWithoutHead() {
Node tmp = head.next;
int length = 1;
// 選周遊一遍拿到連結清單長度
while (tmp.next != null) {
tmp = tmp.next;
length++;
}
// 再周遊一遍拿到連結清單中間結點
tmp = head.next;
int middleLength = length / 2;
while (middleLength > 0) {
tmp = tmp.next;
middleLength--;
}
return tmp;
} 解法三
解法二由于要周遊兩次連結清單，顯得不是那麼高效，那能否隻周遊一次連結清單就能拿到中間結點呢。
這裡就引入我們的快慢指針了，主要有三步
1、 快慢指針同時指向 head 的後繼結點
2、 慢指針走一步，快指針走兩步
3、 不斷地重複步驟2，什麼時候停下來呢，這取決于連結清單的長度是奇數還是偶數
- 如果連結清單長度為奇數,當 fast.next = null 時,slow 為中間結點
- 如果連結清單長度為偶數,當 fast = null 時,slow 為中間結點
- 由以上分析可知:當 fast = null 或者 fast.next = null 時，此時的 slow 結點即為我們要求的中間結點,否則不斷地重複步驟 2， 知道了思路，代碼實作就簡單了
/**
* 使用快慢指針查找找到中間結點
* @return
*/
public Node findMiddleNodeWithSlowFastPointer() {
Node slow = head.next;
Node fast = head.next;
while (fast != null && fast.next != null) {
// 快指針走兩步
fast = fast.next.next;
// 慢指針走一步
slow = slow.next;
}
// 此時的 slow 結點即為哨兵結點
return slow;
} 有了上面的基礎，我們現在再大一下難度，看下下面這道題
輸入一個連結清單，輸出該連結清單中的倒數第 k 個結點。比如連結清單為 head-->1-->2-->3-->4-->5。求倒數第三個結點（即值為 3 的節點）
分析：我們知道如果要求順序的第 k 個結點還是比較簡單的，從 head 開始周遊 k 次即可，如果要求逆序的第 k 個結點，正常的做法是先順序周遊一遍連結清單，拿到連結清單長度，然後再周遊 連結清單長度-k 次即可，這樣要周遊兩次連結清單，不是那麼高效，如何隻周遊一次呢，還是用我們說的快慢指針解法
- 首先讓快慢指針同時指向 head 的後繼結點
- 快指針往前走 k- 1 步,先走到第 k 個結點
- 快慢指針同時往後走一步，不斷重複此步驟，直到快指針走到尾結點,此時的 slow 結點即為我們要找的倒序第 k 個結點
注：需要注意臨界情況：k 大于連結清單的長度，這種異常情況應該抛異常
public Node findKthToTail(int k) throws Exception {
Node slow = head.next;
Node fast = head.next;
// 快指針先移到第k個結點
int tmpK = k - 1;
while (tmpK > 0 && fast != null) {
fast = fast.next;
tmpK--;
}
// 臨界條件：k大于連結清單長度
if (fast == null) {
throw new Exception("K結點不存在異常");
}
// slow 和 fast 同時往後移，直到 fast 走到尾結點
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
} 知道了如何求倒序第 k 個結點，再來看看下面這道題
給定一個單連結清單，設計一個算法實作連結清單向右旋轉 K 個位置。舉例：給定 head->1->2->3->4->5->NULL, K=3,右旋後即為 head->3->4->5-->1->2->NULL
分析：這道題其實是對求倒序第 K 個位置的的一個變形，主要思路如下
- 先找到倒數第 K+1 個結點, 此結點的後繼結點即為倒數第 K 個結點
- 将倒數第 K+1 結點的的後繼結點設定為 null
- 将 head 的後繼結點設定為以上所得的倒數第 K 個結點，将原尾結點的後繼結點設定為原 head 的後繼結點
public void reversedKthToTail(int k) throws Exception {
// 直接調已實作的 尋找倒序k個結點的方法，這裡是 k+1
Node KPreNode = findKthToTail(k+1);
// 倒數第 K 個結點
Node kNode = KPreNode.next;
Node headNext = head.next;
KPreNode.next = null;
head.next = kNode;
// 尋找尾結點
Node tmp = kNode;
while (tmp.next != null) {
tmp = tmp.next;
}
// 尾結點的後繼結點設定為原 head 的後繼結點
tmp.next = headNext;
} 有了上面兩道題的鋪墊，相信下面這道題不是什麼難事，限于篇幅關系，這裡不展開，大家可以自己試試
輸入一個連結清單，删除該連結清單中的倒數第 k 個結點
小試牛刀之二
判斷兩個單連結清單是否相交及找到第一個交點,要求空間複雜度 O(1)。如圖示：如果兩個連結清單相交，5為這兩個連結清單相交的第一個交點
畫外音：如果沒有空間複雜度O(1)的限制，其實有多種解法，一種是周遊連結清單 1，将連結清單 1 的所有的結點都放到一個 set 中，再次周遊連結清單 2，每周遊一個結點，就判斷這個結點是否在 set，如果發現結點在這個 set 中，則這個結點就是連結清單第一個相交的結點
分析：首先我們要明白，由于連結清單本身的性質，如果有一個結點相交，那麼相交結點之後的所有結點都是這兩個連結清單共用的，也就是說兩個連結清單的長度主要相差在相交結點之前的結點長度，于是我們有以下思路
1、如果連結清單沒有定義長度，則我們先周遊這兩個連結清單拿到兩個連結清單長度，假設分别為 L1, L2 (L1 >= L2), 定義 p1, p2 指針分别指向各自連結清單 head 結點，然後 p1 先往前走 L1 - L2 步。這一步保證了 p1，p2 指向的指針與相交結點(如果有的話)一樣近。
2、 然後 p1,p2 不斷往後周遊，每次走一步，邊周遊邊判斷相應結點是否相等，如果相等即為這兩個連結清單的相交結點
public static Node detectCommonNode(LinkedList list1, LinkedList list2) {
int length1 = 0; // 連結清單 list1 的長度
int length2 = 0; // 連結清單 list2 的長度
Node p1 = list1.head;
Node p2 = list2.head;
while (p1.next != null) {
length1++;
p1 = p1.next;
}
while (p2.next != null) {
length2++;
p2 = p2.next;
}
p1 = list1.head;
p2 = list2.head;
// p1 或 p2 前進 |length1-length2| 步
if (length1 >= length2) {
int diffLength = length1-length2;
while (diffLength > 0) {
p1 = p1.next;
diffLength--;
}
} else {
int diffLength = length2-length1;
while (diffLength > 0) {
p2 = p2.next;
diffLength--;
}
}
// p1,p2分别往後周遊，邊周遊邊比較，如果相等，即為第一個相交結點
while (p1 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next;
if (p1.data == p2.data) {
// p1，p2 都為相交結點，傳回 p1 或 p2
return p1;
}
}
// 沒有相交結點，傳回空指針
return null;
} 進階
接下來我們來看如何用快慢指針來判斷連結清單是否有環,這是快慢指針最常見的用法
判斷連結清單是否有環，如果有，找到環的入口位置（下圖中的 2），要求空間複雜度為O(1)
首先我們要看如果連結清單有環有什麼規律，如果從 head 結點開始周遊，則這個周遊指針一定會在以上的環中繞圈子，是以我們可以分别定義快慢指針，慢指針走一步，快指針走兩步， 由于最後快慢指針在周遊過程中一直會在圈中裡繞，且快慢指針每次的周遊步長不一樣，是以它們在裡面不斷繞圈子的過程一定會相遇，就像 5000 米長跑，一人跑的快，一人快的慢，跑得快的人一定會追上跑得慢的（即套圈）。
還不明白？那我們簡單證明一下
1、 假如快指針離慢指針相差一個結點,則再一次周遊，慢指針走一步，快指針走兩步，相遇
2、 假如快指針離慢指針相差兩個結點,則再一次周遊，慢指針走一步，快指針走兩步，相差一個結點，轉成上述 1 的情況
3、 假如快指針離慢指針相差 N 個結點（N大于2），則下一次周遊由于慢指針走一步，快指針走兩步，是以相差 N+1-2 = N-1 個結點，發現了嗎，相差的結點從 N 變成了 N-1,縮小了！不斷地周遊，相差的結點會不斷地縮小，當 N 縮小為 2 時，即轉為上述步驟 2 的情況，由此得證，如果有環，快慢指針一定會相遇！
畫外音：如果慢指針走一步，快指針走的不是兩步，而是大于兩步，會有什麼問題，大家可以考慮一下
public Node detectCrossNode() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == null) {
return null;
}
if (slow.data == fast.data) {
return slow;
}
}
return null;
} 判斷有環為啥要傳回相遇的結點，而不是傳回 true 或 false 呢。因為題目中還有一個要求，判斷環的入口位置，就是為了這個做鋪墊的,一起來看看怎麼找環的入口，需要一些分析的技巧
假設上圖中的 7 為快慢指針相遇的結點，不難分析出相遇時慢指針走了 L + S 步，快指針呢，它走得比慢指針更快，它除了走了 L + S 步外，還額外在環裡繞了 n 圈，是以快指針走了 L+S+nR 步（R為圖中環的長度）,另外我們知道每周遊一次，慢指針走了一步，快指針走了兩步，是以快指針走的路程是慢指針的兩倍,即 2 (L+S) = L+S+nR，可得 L+S = nR
- 當 n = 1 時，則 L+S = R 時,則從相遇點 7 開始周遊走到環入口點 2 的距離為 R - S = L，剛好是環的入口結點,而 head 與環入口點 2 的距離恰好也為 L，是以隻要在頭結點定義一個指針，在相遇點（7）定義另外一個指針，兩個指針同時周遊，每次走一步，必然在環的入口位置 2 相遇
- 當 n > 1 時，L + S = nR,即 L = nR - S, nR-S 怎麼了解？如果指針指向相遇結點 7 ，則此指針走了 n 圈後，回退 S 步，此時剛好指向環入口位置，也就是說如果設定一個指針指向 head（定義為p1）, 另設一個指針指向 7（定義為p2），不斷周遊，p2 走了 nR-S 時（即環的入口位置），p1也剛好走到這裡（此時 p1 走了 nR-S = L步，剛好是環入口位置），即兩者相遇！
綜上所述，要找到入口結點，隻需定義兩個指針，一個指針指向 head, 一個指針指向快慢指針的相遇點，然後這兩個指針不斷周遊（每次走一步），當它們指向同一個結點時即是環的入口結點
public Node getRingEntryNode() {
// 擷取快慢指針相遇結點
Node crossNode = detectCrossNode();
// 如果沒有相遇點，則沒有環
if (crossNode == null) {
return null;
}
// 分别定義兩個指針，一個指向頭結點，一個指向快慢指針相交結點
Node tmp1 = head;
Node tmp2 = crossNode;
// 兩者相遇點即為環的入口結點
while (tmp1.data != tmp2.data) {
tmp1 = tmp1.next;
tmp2 = tmp2.next;
}
return tmp1;
} 思考題：知道了環的入口結點，怎麼求環的長度？
總結
本文總結了連結清單的快慢指針常用解題技巧，分别總結了兩大類的問題：尋找第 K 個結點以及判斷環及其入口結點，加上上文中提到的連結清單翻轉技巧，這兩大類都是面試中非常熱門的考點，其他的面試題多是在這兩大類上進行變形，建立大家好好敲一遍代碼。
-----------------------
公衆号：五分鐘學算法（ID：CXYxiaowu）
部落格：www.cxyxiaowu.com
知乎：程式員吳師兄
一個正在學習算法的人，緻力于将算法講清楚！
長按下圖二維碼關注，和你一起領悟算法的魅力。