力扣原題鏈接: 141. 環形鏈表 - 力扣（LeetCode）

哈希表

檢測環形鏈表, 直觀的思路就是使用哈希表, 遍歷這個鏈表, 將訪問過的節點加入到哈希表中, 如果遍歷過程中發現節點已經存在于哈希表中, 則說明鏈表有環.

復雜度分析:

• 時間復雜度: O(N), 最壞情況下需要遍歷所有節點.
• 空間復雜度: O(N), 最壞情況下每個節點都會加入到哈希表.

Floyd判圈算法

另一種更高效的算法是Floyd判圈算法, 又稱龜兔賽跑算法, 該算法由計算機科學家羅伯特·弗洛伊德(Robert W. Floyd)提出, 其核心思想是通過兩個指針以不同速度遍歷鏈表來判斷是否存在環, 并可以進一步確定環的起點和長度.

算法步驟

初始化兩個指針:

• 慢指針: 每次移動一步
• 快指針: 每次移動兩步

兩個指針同時從起點出發, 按照各自的速度移動.

判斷是否有環:

• 如果快指針會先到達終點, 則說明鏈表無環
• 如果快慢指針相遇, 則說明鏈表有環

?

動畫演示

歡迎關注公眾號: 算法鐵金庫

持續更新數據結構與算法, 動畫演示, 理解算法快人一步~

Java代碼:

public class Solution {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode slow = head;ListNode fast = head;do {slow = slow.next;if (fast.next != null && fast.next.next != null) {fast = fast.next.next;} else {return false;}} while (slow != fast);return true;}
}

?

復雜度分析:

• 時間復雜度: O(N), 慢指針對每個節點至多訪問一次, 快指針訪問的節點個數不超過慢指針的2倍.
• 空間復雜度: O(1), 只需要兩個額外指針.

?

思考: 為什么當鏈表有環, 快慢指針一定能相遇?

如果存在環, 快指針每次比慢指針多走一步, 也就是說距離每次減1, 所以最終一定能相遇.

擴展應用

確定環的起點

當快慢指針首次相遇后, 將其中一個指針移回起點(如慢指針), 然后兩個指針改為每次均移動一步. 當它們再次相遇時, 相遇點即為環的起點.

?

證明:

用a表示鏈表頭到環起點的距離

用L表示環的長度

第一階段: 尋找相遇點

• 當慢指針走了a步到達環起點時, 快指針已經走了2a步
• 快指針在環中的位置是 (2a - a) % L = a % L (因為前a步用來走到環起點)
• 此時快指針需要追趕慢指針, 相對距離是 L - a % L
• 由于快指針每次比慢指針多走1步, 經過 L - a % L 步后兩者相遇
• L - a % L 就是慢指針在環中移動的長度, 也就是相遇位置距環起點的距離

第二階段: 確定環起點

• 將慢指針移回鏈表頭部, 快指針不動, 接下來兩個指針每次各走1步
• 慢指針走了a步到達環起點, 同時快指針也走了a步, 在環中的位置為 L - a % L + a
• 而 (L - a % L + a) % L = 0, 也就是說該位置就是環起點.

證畢.

計算環的長度

在確定有環后, 固定一個指針, 另一個指針繼續移動并計數, 直到再次相遇, 計數結果即為環的長度.

?

?