阿竺 ·1. 前言
上個章節介紹了單鏈表反轉，單鏈表還存在一些經典的問題，例如找到鏈表的倒數第 K 個節點，或者在原始鏈表上進行快速排序，或者是判斷一個單鏈表是否成環，這些問題看似沒有共同性，但是都可以使用快慢指針（Fast-Slow Point）方法解決。
2. 鏈表成環問題
面試官提問：給定一個單鏈表，判斷鏈表是否存在環？能否在不使用額外空間的情況下解決問題？
題目解析：
鏈表成環問題是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode.com/problems/linked-list-cycle/。
暴力破解方法是使用額外的數組結構，數組每一個元素存儲鏈表的值以及節點哈希地址，在遍歷鏈表的時候，如果發現遍歷到相同哈希地址的節點，說明鏈表有環，否則直到遍歷到鏈表末尾節點為止。
但是面試官要求在原始數組上操作，空間復雜度控制在O（1）。
使用單個指針則沒有記憶能力，所以肯定要使用兩個以上的指針遍歷鏈表，最常用解法就是快慢指針法。
經典快慢指針的算法核心思路是：
（1）初始定義：定義一個指針 slow，每次走一個 Node 節點；定義一個指針 fast，每次走兩個 Node 節點；
（2）終止條件一：當快指針走到了 Null 節點，說明鏈表沒有成環；
（3）終止條件二：當快指針和慢指針同時走到了一個節點，說明該鏈表有環；
（4）附加計算一：當滿足鏈表有環時，將慢指針重置到鏈表頭部，然后快慢指針同時走，每次只走一個節點，當兩個指針再次相遇時，相遇點即是鏈表的環入口；
（5）附加計算二：當滿足鏈表有環時，停止快指針，每次慢指針走一個 Node 節點，當兩個節點再次相遇時，慢指針重新走的長度即是鏈表長度。
最重要的環節在于如何證明慢指針和快指針會在環中相遇，我們假設一個通用的有環鏈表如下圖所示：
其中A—>B 的距離為 x，B—>C 的距離為y，C—>B 的距離為 z。
假設慢指針走了a步，那么快指針走了2a步，因為相遇時快指針已經在環上循環了n次，所以滿足公式：
2*(x+y) = x+y+n*(y+z)，所以x+y = n * (y+z)?？炻羔樦g的距離會逐漸增大，結果是要么快指針提前走到了鏈表末尾，要么是快指針剛好多走出n個鏈表長度，說明鏈表有環。
我們在白板上可以寫出算法實現，示例：
public class Solution {
public boolean hasCycle(ListNode head) {
//如果鏈表為空或者只有一個節點，肯定不成環
if(head==null || head.next==null){
return false;
}
ListNode slow = head;
head=head.next;
while(head!=null && head.next!=null){
//當快慢指針相遇，說明鏈表有環
if(slow==head){
return true;
}
slow=slow.next;
head=head.next.next;
}
return false;
}
}
算法的時間復雜度為O（N），其中N表示鏈表長度，空間復雜度為O（1），因為沒有使用額外輔助空間。
3. 小結
本章節介紹了最基礎的快慢指針算法，快慢指針是解決鏈表問題的銀彈。例如找到鏈表的倒數 K 個節點，也可以另快慢指針間距為 K，兩者步長相同，最終慢指針走到的節點即是目標節點。對于快慢指針用法，候選人需要注意兩點： ① 邊界條件：如果是空鏈表或者單節點鏈表，直接使用快慢指針可能會導致空指針異常，需要特殊處理； ② 快慢指針不一定是步長相差兩倍，可能是步長相同，但是一個走在前，一個走在后。
2025 imooc.com All Rights Reserved |