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