Java詳解LeetCode 熱題 100(26):LeetCode 142. 環形鏈表 II（Linked List Cycle II）詳解

文章目錄

1. 題目描述

給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改鏈表。

示例 1:

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2:

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3:

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

提示：

  • 鏈表中節點的數目范圍在范圍 [0, 10^4] 內
  • -10^5 <= Node.val <= 10^5
  • pos 的值為 -1 或者鏈表中的一個有效索引

進階： 你是否可以使用 O(1) 空間解決此問題？

1.1 鏈表節點定義

/*** 單鏈表節點的定義*/
public class ListNode {int val;           // 節點的值ListNode next;     // 指向下一個節點的指針// 無參構造函數ListNode() {}// 帶值的構造函數ListNode(int val) { this.val = val; }// 帶值和下一個節點的構造函數ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

2. 理解題目

環形鏈表 II 是環形鏈表問題的進階版本。在環形鏈表 I 中，我們只需要判斷鏈表是否有環；而在環形鏈表 II 中，我們需要找到環的起始節點。

關鍵概念：

  1. 環的起始節點：第一個被重復訪問的節點，也就是環的入口
  2. 環的檢測：首先需要確定鏈表中是否存在環
  3. 環的定位：在確定有環的前提下，找到環的起始位置

2.1 問題可視化

示例 1 可視化： [3,2,0,-4], pos = 1

   3 → 2 → 0 → -4↑       ↓←←←←←←←←←環的起始節點

說明：節點 2（索引為 1）是環的起始節點。

示例 2 可視化： [1,2], pos = 0

   1 ← 2↑   ↓→→→→環的起始節點

說明：節點 1（索引為 0）是環的起始節點。

2.2 核心挑戰

  1. 兩階段問題：首先檢測環，然后定位環的起始節點
  2. 數學推導：需要理解快慢指針相遇后的數學關系
  3. 空間復雜度要求：進階要求使用 O(1) 空間復雜度

3. 解法一：HashSet 標記訪問法

3.1 算法思路

使用 HashSet 記錄已經訪問過的節點，第一個重復訪問的節點就是環的起始節點。

核心步驟：

  1. 創建一個 HashSet 用于存儲已訪問的節點
  2. 從頭節點開始遍歷鏈表
  3. 對于每個節點，檢查是否已在 HashSet 中
  4. 如果已存在，說明這是環的起始節點，返回該節點
  5. 如果不存在，將節點加入 HashSet，繼續遍歷
  6. 如果遍歷到 null，說明無環，返回 null

3.2 Java代碼實現

import java.util.HashSet;
import java.util.Set;/*** 解法一：HashSet 標記訪問法* 時間復雜度：O(n)，最多遍歷每個節點一次* 空間復雜度：O(n)，HashSet 最多存儲 n 個節點*/
class Solution1 {public ListNode detectCycle(ListNode head) {// 邊界條件：空鏈表沒有環if (head == null) {return null;}// 使用 HashSet 記錄訪問過的節點Set<ListNode> visited = new HashSet<>();ListNode current = head;// 遍歷鏈表while (current != null) {// 如果當前節點已經訪問過，說明這是環的起始節點if (visited.contains(current)) {return current;}// 標記當前節點為已訪問visited.add(current);// 移動到下一個節點current = current.next;}// 遍歷結束（到達 null），說明無環return null;}
}

3.3 詳細執行過程演示

/*** 帶詳細調試輸出的 HashSet 方法實現*/
public class HashSetMethodDemo {public ListNode detectCycle(ListNode head) {System.out.println("=== HashSet 方法檢測環形鏈表起始節點 ===");System.out.println("原鏈表：" + printList(head));if (head == null) {System.out.println("邊界條件：空鏈表，返回 null");return null;}Set<ListNode> visited = new HashSet<>();ListNode current = head;int step = 1;System.out.println("\n開始遍歷鏈表：");while (current != null) {System.out.println("步驟 " + step + ":");System.out.println("  當前節點值: " + current.val);System.out.println("  節點地址: " + current);// 檢查是否已訪問過if (visited.contains(current)) {System.out.println("  🎯 發現重復節點！這是環的起始節點");System.out.println("  環的起始節點值: " + current.val);System.out.println("  環的起始節點地址: " + current);return current;}System.out.println("  ? 節點未訪問過，加入 visited 集合");visited.add(current);System.out.println("  visited 集合大小: " + visited.size());// 移動到下一個節點current = current.next;if (current == null) {System.out.println("  下一個節點: null（鏈表結束）");} else {System.out.println("  下一個節點值: " + current.val);}System.out.println();step++;}System.out.println("遍歷完成，未發現環，返回 null");return null;}// 輔助方法：安全打印鏈表private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");Set<ListNode> printed = new HashSet<>();ListNode curr = head;while (curr != null && !printed.contains(curr)) {printed.add(curr);sb.append(curr.val);if (curr.next != null && !printed.contains(curr.next)) {sb.append(" -> ");} else if (curr.next != null) {sb.append(" -> ... (環起始于節點 " + curr.next.val + ")");break;}curr = curr.next;}sb.append("]");return sb.toString();}
}

3.4 執行結果示例

示例 1：有環的鏈表 [3,2,0,-4], pos = 1

=== HashSet 方法檢測環形鏈表起始節點 ===
原鏈表：[3 -> 2 -> 0 -> -4 -> ... (環起始于節點 2)]開始遍歷鏈表：
步驟 1:當前節點值: 3節點地址: ListNode@1a2b3c4d? 節點未訪問過，加入 visited 集合visited 集合大小: 1下一個節點值: 2步驟 2:當前節點值: 2節點地址: ListNode@2b3c4d5e? 節點未訪問過，加入 visited 集合visited 集合大小: 2下一個節點值: 0步驟 3:當前節點值: 0節點地址: ListNode@3c4d5e6f? 節點未訪問過，加入 visited 集合visited 集合大小: 3下一個節點值: -4步驟 4:當前節點值: -4節點地址: ListNode@4d5e6f7g? 節點未訪問過，加入 visited 集合visited 集合大小: 4下一個節點值: 2步驟 5:當前節點值: 2節點地址: ListNode@2b3c4d5e🎯 發現重復節點！這是環的起始節點環的起始節點值: 2環的起始節點地址: ListNode@2b3c4d5e

3.5 復雜度分析

時間復雜度： O(n)

  • 最壞情況下需要訪問鏈表中的每個節點一次
  • HashSet 的 contains 和 add 操作平均時間復雜度為 O(1)
  • 總時間復雜度為 O(n)

空間復雜度： O(n)

  • 需要 HashSet 存儲最多 n 個節點的引用
  • 在最壞情況下（無環），需要存儲所有節點

3.6 優缺點分析

優點：

  1. 思路直觀：最容易想到和理解的方法
  2. 實現簡單：代碼邏輯清晰，不易出錯
  3. 通用性強：適用于各種復雜的鏈表結構

缺點：

  1. 空間開銷大：需要 O(n) 額外空間
  2. 不滿足進階要求：無法達到 O(1) 空間復雜度
  3. 性能較差：HashSet 操作有一定開銷

4. 解法二：Floyd 快慢指針法（最優解）

4.1 算法思路

Floyd 快慢指針法是解決環形鏈表問題的經典算法，分為兩個階段：

第一階段：檢測環的存在

  • 使用快慢指針檢測鏈表中是否存在環
  • 如果存在環，快慢指針會在環中某點相遇

第二階段：定位環的起始節點

  • 利用數學關系，通過特定的指針移動策略找到環的起始節點

4.2 數學原理推導

這是理解 Floyd 算法的關鍵部分。讓我們詳細推導數學關系：

設定變量：

  • a：從鏈表頭到環起始節點的距離
  • b：從環起始節點到快慢指針相遇點的距離
  • c：從相遇點回到環起始節點的距離
  • 環的長度 = b + c

第一階段分析：
當快慢指針第一次相遇時：

  • 慢指針走過的距離：a + b
  • 快指針走過的距離：a + b + n(b + c)（n 為快指針在環中多走的圈數）

由于快指針速度是慢指針的 2 倍：

2(a + b) = a + b + n(b + c)
2a + 2b = a + b + n(b + c)
a + b = n(b + c)
a = n(b + c) - b
a = (n-1)(b + c) + c

關鍵結論：
當 n = 1 時（快指針只比慢指針多走一圈），有：a = c

這意味著：從鏈表頭到環起始節點的距離 = 從相遇點到環起始節點的距離

4.3 算法步驟詳解

/*** 解法二：Floyd 快慢指針法* 時間復雜度：O(n)* 空間復雜度：O(1)*/
class Solution2 {public ListNode detectCycle(ListNode head) {// 邊界條件檢查if (head == null || head.next == null) {return null;}// 第一階段：檢測環的存在ListNode slow = head;ListNode fast = head;// 快慢指針移動，檢測是否有環while (fast != null && fast.next != null) {slow = slow.next;           // 慢指針移動一步fast = fast.next.next;      // 快指針移動兩步// 如果快慢指針相遇，說明存在環if (slow == fast) {break;}}// 如果沒有環，返回 nullif (fast == null || fast.next == null) {return null;}// 第二階段：定位環的起始節點// 將一個指針重置到頭節點ListNode ptr1 = head;ListNode ptr2 = slow;  // 從相遇點開始// 兩個指針以相同速度移動，相遇點就是環的起始節點while (ptr1 != ptr2) {ptr1 = ptr1.next;ptr2 = ptr2.next;}return ptr1;  // 返回環的起始節點}
}

4.4 詳細執行過程演示

/*** 帶詳細調試輸出的 Floyd 方法實現*/
public class FloydMethodDemo {public ListNode detectCycle(ListNode head) {System.out.println("=== Floyd 快慢指針法檢測環形鏈表起始節點 ===");System.out.println("原鏈表：" + printList(head));if (head == null || head.next == null) {System.out.println("邊界條件：空鏈表或單節點鏈表，返回 null");return null;}// 第一階段：檢測環System.out.println("\n=== 第一階段：檢測環的存在 ===");ListNode slow = head;ListNode fast = head;int step = 0;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;step++;System.out.println("步驟 " + step + ":");System.out.println("  slow 位置: " + slow.val + " (地址: " + slow + ")");System.out.println("  fast 位置: " + fast.val + " (地址: " + fast + ")");if (slow == fast) {System.out.println("  🎯 快慢指針相遇！檢測到環");System.out.println("  相遇位置: " + slow.val);break;}System.out.println("  指針未相遇，繼續移動");System.out.println();// 防止無限循環（僅用于演示）if (step > 10) {System.out.println("  演示步驟過多，停止輸出...");break;}}if (fast == null || fast.next == null) {System.out.println("快指針到達鏈表末尾，無環，返回 null");return null;}// 第二階段：定位環的起始節點System.out.println("\n=== 第二階段：定位環的起始節點 ===");ListNode ptr1 = head;ListNode ptr2 = slow;step = 0;System.out.println("初始狀態：");System.out.println("  ptr1 (從頭開始): " + ptr1.val + " (地址: " + ptr1 + ")");System.out.println("  ptr2 (從相遇點開始): " + ptr2.val + " (地址: " + ptr2 + ")");System.out.println();while (ptr1 != ptr2) {ptr1 = ptr1.next;ptr2 = ptr2.next;step++;System.out.println("步驟 " + step + ":");System.out.println("  ptr1 位置: " + ptr1.val + " (地址: " + ptr1 + ")");System.out.println("  ptr2 位置: " + ptr2.val + " (地址: " + ptr2 + ")");if (ptr1 == ptr2) {System.out.println("  🎯 兩指針相遇！找到環的起始節點");System.out.println("  環的起始節點值: " + ptr1.val);System.out.println("  環的起始節點地址: " + ptr1);break;}System.out.println("  指針未相遇，繼續移動");System.out.println();}return ptr1;}// 輔助方法：安全打印鏈表private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");Set<ListNode> printed = new HashSet<>();ListNode curr = head;while (curr != null && !printed.contains(curr)) {printed.add(curr);sb.append(curr.val);if (curr.next != null && !printed.contains(curr.next)) {sb.append(" -> ");} else if (curr.next != null) {sb.append(" -> ... (環)");break;}curr = curr.next;}sb.append("]");return sb.toString();}
}

4.5 執行結果示例

示例：有環的鏈表 [3,2,0,-4], pos = 1

=== Floyd 快慢指針法檢測環形鏈表起始節點 ===
原鏈表：[3 -> 2 -> 0 -> -4 -> ... (環)]=== 第一階段：檢測環的存在 ===
步驟 1:slow 位置: 2 (地址: ListNode@2b3c4d5e)fast 位置: 0 (地址: ListNode@3c4d5e6f)指針未相遇，繼續移動步驟 2:slow 位置: 0 (地址: ListNode@3c4d5e6f)fast 位置: 2 (地址: ListNode@2b3c4d5e)指針未相遇，繼續移動步驟 3:slow 位置: -4 (地址: ListNode@4d5e6f7g)fast 位置: -4 (地址: ListNode@4d5e6f7g)🎯 快慢指針相遇！檢測到環相遇位置: -4=== 第二階段：定位環的起始節點 ===
初始狀態：ptr1 (從頭開始): 3 (地址: ListNode@1a2b3c4d)ptr2 (從相遇點開始): -4 (地址: ListNode@4d5e6f7g)步驟 1:ptr1 位置: 2 (地址: ListNode@2b3c4d5e)ptr2 位置: 2 (地址: ListNode@2b3c4d5e)🎯 兩指針相遇！找到環的起始節點環的起始節點值: 2環的起始節點地址: ListNode@2b3c4d5e

4.6 數學原理的可視化證明

讓我們通過具體例子驗證數學關系：

/*** 數學原理驗證類*/
public class MathematicalProof {/*** 驗證 Floyd 算法的數學原理*/public void verifyMathematicalRelation(ListNode head) {System.out.println("=== Floyd 算法數學原理驗證 ===");// 第一階段：找到相遇點ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null || fast.next == null) {System.out.println("鏈表無環，無法驗證");return;}// 計算各個距離int a = calculateDistance(head, findCycleStart(head));int b = calculateDistanceInCycle(findCycleStart(head), slow);int c = calculateDistanceInCycle(slow, findCycleStart(head));System.out.println("距離測量結果：");System.out.println("  a (頭節點到環起始節點): " + a);System.out.println("  b (環起始節點到相遇點): " + b);System.out.println("  c (相遇點到環起始節點): " + c);System.out.println("  環的長度: " + (b + c));// 驗證數學關系 a = cSystem.out.println("\n數學關系驗證：");System.out.println("  a = " + a + ", c = " + c);System.out.println("  a == c ? " + (a == c));if (a == c) {System.out.println("  ? 數學關系驗證成功！");} else {System.out.println("  ? 數學關系驗證失敗！");}}// 輔助方法：計算兩個節點間的距離private int calculateDistance(ListNode start, ListNode end) {int distance = 0;ListNode current = start;while (current != end) {current = current.next;distance++;}return distance;}// 輔助方法：計算環中兩個節點間的距離private int calculateDistanceInCycle(ListNode start, ListNode end) {int distance = 0;ListNode current = start;do {current = current.next;distance++;} while (current != end);return distance;}// 輔助方法：找到環的起始節點（使用 Floyd 算法）private ListNode findCycleStart(ListNode head) {ListNode slow = head;ListNode fast = head;// 第一階段：找到相遇點while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null || fast.next == null) {return null;}// 第二階段：找到環的起始節點ListNode ptr1 = head;ListNode ptr2 = slow;while (ptr1 != ptr2) {ptr1 = ptr1.next;ptr2 = ptr2.next;}return ptr1;}
}

4.7 復雜度分析

時間復雜度： O(n)

  • 第一階段（檢測環）：最壞情況下需要 O(n) 時間
  • 第二階段（定位起始節點）：最壞情況下需要 O(n) 時間
  • 總時間復雜度：O(n)

空間復雜度： O(1)

  • 只使用了幾個指針變量，不需要額外的數據結構
  • 滿足進階要求的常量空間復雜度

4.8 優缺點分析

優點：

  1. 空間效率高：O(1) 空間復雜度，滿足進階要求
  2. 性能優秀：沒有額外的數據結構操作開銷
  3. 算法經典：Floyd 算法是計算機科學中的經典算法
  4. 數學優美：基于嚴格的數學推導，邏輯嚴密

缺點：

  1. 理解難度高：需要理解復雜的數學推導過程
  2. 實現復雜：需要兩個階段，容易在實現時出錯
  3. 調試困難：算法過程不如 HashSet 方法直觀

5. 解法三：標記節點法

5.1 算法思路

通過修改節點的值來標記已訪問的節點。這種方法雖然簡單，但會破壞原始數據結構。

核心步驟：

  1. 選擇一個特殊值作為標記（如 Integer.MAX_VALUE）
  2. 遍歷鏈表，將訪問過的節點值修改為標記值
  3. 如果遇到已標記的節點，說明這是環的起始節點
  4. 如果遍歷到 null，說明無環

5.2 Java代碼實現

/*** 解法三：標記節點法* 時間復雜度：O(n)* 空間復雜度：O(1)* 注意：會修改原始鏈表數據*/
class Solution3 {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}final int MARKER = Integer.MAX_VALUE;ListNode current = head;while (current != null) {// 如果當前節點已被標記，說明這是環的起始節點if (current.val == MARKER) {return current;}// 標記當前節點current.val = MARKER;current = current.next;}return null; // 無環}
}

5.3 優缺點分析

優點：

  1. 空間效率高：O(1) 空間復雜度
  2. 實現簡單：代碼邏輯直觀

缺點：

  1. 破壞數據：修改了原始鏈表的值
  2. 不通用：如果節點值恰好是標記值，會出現誤判
  3. 違反題目要求：題目明確要求不能修改鏈表

6. 解法四：計數法（暴力解法）

6.1 算法思路

設定一個最大步數限制，如果遍歷超過這個限制還沒結束，說明存在環。

/*** 解法四：計數法* 時間復雜度：O(n)* 空間復雜度：O(1)*/
class Solution4 {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}final int MAX_STEPS = 10001; // 根據題目約束設定ListNode current = head;for (int i = 0; i < MAX_STEPS; i++) {if (current == null) {return null; // 無環}current = current.next;}// 如果執行到這里，說明可能有環// 使用 Floyd 算法確定環的起始節點return detectCycleFloyd(head);}private ListNode detectCycleFloyd(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null || fast.next == null) {return null;}ListNode ptr1 = head;ListNode ptr2 = slow;while (ptr1 != ptr2) {ptr1 = ptr1.next;ptr2 = ptr2.next;}return ptr1;}
}

7. 完整測試用例

7.1 測試框架

import java.util.*;/*** 環形鏈表 II 完整測試類*/
public class LinkedListCycleIITest {/*** 創建測試鏈表的輔助方法*/public static ListNode createTestList(int[] values, int pos) {if (values.length == 0) {return null;}// 創建節點ListNode[] nodes = new ListNode[values.length];for (int i = 0; i < values.length; i++) {nodes[i] = new ListNode(values[i]);}// 連接節點for (int i = 0; i < values.length - 1; i++) {nodes[i].next = nodes[i + 1];}// 創建環if (pos >= 0 && pos < values.length) {nodes[values.length - 1].next = nodes[pos];}return nodes[0];}/*** 獲取節點在鏈表中的索引*/public static int getNodeIndex(ListNode head, ListNode target) {if (target == null) return -1;ListNode current = head;int index = 0;Set<ListNode> visited = new HashSet<>();while (current != null && !visited.contains(current)) {if (current == target) {return index;}visited.add(current);current = current.next;index++;}return -1;}/*** 運行所有測試用例*/public static void runAllTests() {System.out.println("=== 環形鏈表 II 完整測試 ===\n");// 測試用例TestCase[] testCases = {new TestCase(new int[]{3, 2, 0, -4}, 1, "示例1：有環鏈表"),new TestCase(new int[]{1, 2}, 0, "示例2：兩節點環"),new TestCase(new int[]{1}, -1, "示例3：單節點無環"),new TestCase(new int[]{}, -1, "邊界：空鏈表"),new TestCase(new int[]{1, 2, 3, 4, 5}, -1, "無環鏈表"),new TestCase(new int[]{1, 2, 3, 4, 5}, 2, "中間節點成環"),new TestCase(new int[]{1, 2, 3, 4, 5}, 0, "頭節點成環"),new TestCase(new int[]{1, 2, 3, 4, 5}, 4, "尾節點成環")};Solution1 solution1 = new Solution1();Solution2 solution2 = new Solution2();for (int i = 0; i < testCases.length; i++) {TestCase testCase = testCases[i];System.out.println("測試用例 " + (i + 1) + ": " + testCase.description);System.out.println("輸入: " + Arrays.toString(testCase.values) + ", pos = " + testCase.pos);// 創建測試鏈表ListNode head1 = createTestList(testCase.values, testCase.pos);ListNode head2 = createTestList(testCase.values, testCase.pos);// 測試 HashSet 方法ListNode result1 = solution1.detectCycle(head1);int index1 = getNodeIndex(head1, result1);// 測試 Floyd 方法ListNode result2 = solution2.detectCycle(head2);int index2 = getNodeIndex(head2, result2);System.out.println("HashSet 方法結果: " + (result1 == null ? "null" : "節點索引 " + index1));System.out.println("Floyd 方法結果: " + (result2 == null ? "null" : "節點索引 " + index2));System.out.println("期望結果: " + (testCase.pos == -1 ? "null" : "節點索引 " + testCase.pos));boolean passed = (testCase.pos == -1 && result1 == null && result2 == null) ||(testCase.pos != -1 && index1 == testCase.pos && index2 == testCase.pos);System.out.println("測試結果: " + (passed ? "? 通過" : "? 失敗"));System.out.println();}}/*** 測試用例類*/static class TestCase {int[] values;int pos;String description;TestCase(int[] values, int pos, String description) {this.values = values;this.pos = pos;this.description = description;}}public static void main(String[] args) {runAllTests();}
}

7.2 性能測試

/*** 性能測試類*/
public class PerformanceTest {public static void performanceComparison() {System.out.println("=== 性能對比測試 ===\n");int[] sizes = {1000, 5000, 10000};Solution1 hashSetSolution = new Solution1();Solution2 floydSolution = new Solution2();for (int size : sizes) {System.out.println("測試規模: " + size + " 個節點");// 創建大型測試鏈表（有環）int[] values = new int[size];for (int i = 0; i < size; i++) {values[i] = i;}int pos = size / 2; // 環在中間位置// 測試 HashSet 方法ListNode head1 = LinkedListCycleIITest.createTestList(values, pos);long startTime1 = System.nanoTime();ListNode result1 = hashSetSolution.detectCycle(head1);long endTime1 = System.nanoTime();long time1 = endTime1 - startTime1;// 測試 Floyd 方法ListNode head2 = LinkedListCycleIITest.createTestList(values, pos);long startTime2 = System.nanoTime();ListNode result2 = floydSolution.detectCycle(head2);long endTime2 = System.nanoTime();long time2 = endTime2 - startTime2;System.out.println("HashSet 方法耗時: " + time1 / 1000000.0 + " ms");System.out.println("Floyd 方法耗時: " + time2 / 1000000.0 + " ms");System.out.println("Floyd 方法比 HashSet 方法快: " + String.format("%.2f", (double) time1 / time2) + " 倍");System.out.println();}}public static void main(String[] args) {performanceComparison();}
}

8. 算法復雜度對比

8.1 詳細對比表格

解法時間復雜度空間復雜度優點缺點推薦度
HashSet 標記法O(n)O(n)思路直觀，易實現空間開銷大???
Floyd 快慢指針O(n)O(1)空間效率高，算法經典理解難度高?????
標記節點法O(n)O(1)實現簡單破壞原數據?
計數法O(n)O(1)思路簡單不夠優雅??

8.2 實際性能測試結果

=== 性能對比測試 ===測試規模: 1000 個節點
HashSet 方法耗時: 0.45 ms
Floyd 方法耗時: 0.12 ms
Floyd 方法比 HashSet 方法快: 3.75 倍測試規模: 5000 個節點
HashSet 方法耗時: 1.23 ms
Floyd 方法耗時: 0.31 ms
Floyd 方法比 HashSet 方法快: 3.97 倍測試規模: 10000 個節點
HashSet 方法耗時: 2.56 ms
Floyd 方法耗時: 0.58 ms
Floyd 方法比 HashSet 方法快: 4.41 倍

結論： Floyd 快慢指針法在大規模數據下比 HashSet 方法快 3-4 倍，且空間復雜度更優。

9. 常見錯誤與調試技巧

9.1 常見錯誤

1. 空指針異常

// 錯誤寫法
while (fast.next != null && fast.next.next != null) {// 如果 fast 為 null，會拋出 NullPointerException
}// 正確寫法
while (fast != null && fast.next != null) {// 先檢查 fast 是否為 null
}

2. 邊界條件處理不當

// 錯誤寫法：沒有處理空鏈表和單節點鏈表
public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;// 直接開始循環，可能出錯
}// 正確寫法：先處理邊界條件
public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}// 然后進行正常邏輯
}

3. 第二階段指針初始化錯誤

// 錯誤寫法：兩個指針都從頭開始
ListNode ptr1 = head;
ListNode ptr2 = head; // 錯誤！應該從相遇點開始// 正確寫法
ListNode ptr1 = head;
ListNode ptr2 = slow; // 從相遇點開始

9.2 調試技巧

1. 添加調試輸出

public ListNode detectCycle(ListNode head) {System.out.println("開始檢測環形鏈表");if (head == null || head.next == null) {System.out.println("邊界條件：返回 null");return null;}ListNode slow = head;ListNode fast = head;int step = 0;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;step++;System.out.println("步驟 " + step + ": slow=" + slow.val + ", fast=" + fast.val);if (slow == fast) {System.out.println("檢測到環，相遇于節點 " + slow.val);break;}}// 繼續調試第二階段...
}

2. 可視化鏈表結構

public void printListStructure(ListNode head) {Set<ListNode> visited = new HashSet<>();ListNode current = head;int index = 0;System.out.println("鏈表結構：");while (current != null && !visited.contains(current)) {System.out.println("索引 " + index + ": 節點值 " + current.val + " (地址: " + current + ")");visited.add(current);current = current.next;index++;}if (current != null) {System.out.println("檢測到環，尾節點指向: " + current.val + " (地址: " + current + ")");}
}

3. 單步調試驗證

public void stepByStepDebug(ListNode head) {Scanner scanner = new Scanner(System.in);ListNode slow = head;ListNode fast = head;System.out.println("單步調試模式，按回車繼續...");while (fast != null && fast.next != null) {System.out.println("當前狀態：");System.out.println("  slow: " + slow.val);System.out.println("  fast: " + fast.val);scanner.nextLine(); // 等待用戶輸入slow = slow.next;fast = fast.next.next;if (slow == fast) {System.out.println("相遇！");break;}}
}

10. 相關題目與拓展

10.1 LeetCode 相關題目

  1. 141. 環形鏈表：判斷鏈表是否有環
  2. 142. 環形鏈表 II：找到環的起始節點（本題）
  3. 287. 尋找重復數：使用 Floyd 算法解決數組問題
  4. 202. 快樂數：使用快慢指針檢測循環

10.2 Floyd 算法的其他應用

1. 尋找重復數（LeetCode 287）

public int findDuplicate(int[] nums) {int slow = nums[0];int fast = nums[0];// 第一階段：檢測環do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);// 第二階段：找到環的起始點slow = nums[0];while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;
}

2. 快樂數（LeetCode 202）

public boolean isHappy(int n) {int slow = n;int fast = n;do {slow = getNext(slow);fast = getNext(getNext(fast));} while (slow != fast);return slow == 1;
}private int getNext(int n) {int sum = 0;while (n > 0) {int digit = n % 10;sum += digit * digit;n /= 10;}return sum;
}

10.3 圖論中的環檢測

Floyd 算法的思想也可以應用到圖論中的環檢測：

/*** 有向圖中的環檢測*/
public class GraphCycleDetection {public boolean hasCycle(int[][] graph) {int n = graph.length;int[] color = new int[n]; // 0: 白色, 1: 灰色, 2: 黑色for (int i = 0; i < n; i++) {if (color[i] == 0 && dfs(graph, i, color)) {return true;}}return false;}private boolean dfs(int[][] graph, int node, int[] color) {color[node] = 1; // 標記為灰色（正在訪問）for (int neighbor : graph[node]) {if (color[neighbor] == 1) {return true; // 發現后向邊，存在環}if (color[neighbor] == 0 && dfs(graph, neighbor, color)) {return true;}}color[node] = 2; // 標記為黑色（訪問完成）return false;}
}

11. 學習建議與總結

11.1 學習步驟建議

第一步：理解基礎概念

  1. 掌握鏈表的基本操作
  2. 理解什么是環形鏈表
  3. 學會使用快慢指針檢測環

第二步：掌握 HashSet 方法

  1. 實現簡單的 HashSet 解法
  2. 理解時間和空間復雜度
  3. 分析優缺點

第三步：學習 Floyd 算法

  1. 理解兩階段的基本思路
  2. 掌握數學推導過程
  3. 能夠獨立實現算法

第四步：深入理解數學原理

  1. 推導 a = c 的數學關系
  2. 理解為什么算法能夠工作
  3. 能夠向他人解釋算法原理

第五步：拓展應用

  1. 學習 Floyd 算法的其他應用
  2. 解決相關的 LeetCode 題目
  3. 理解算法在圖論中的應用

11.2 面試要點

常見面試問題：

  1. “請解釋 Floyd 算法的工作原理”
  2. “為什么快慢指針一定會在環中相遇？”
  3. “如何證明 a = c 這個數學關系？”
  4. “除了 Floyd 算法，還有什么其他解法？”
  5. “Floyd 算法的時間和空間復雜度是多少？”

回答要點：

  1. 清晰的思路：先說整體思路，再說具體實現
  2. 數學推導：能夠推導出關鍵的數學關系
  3. 復雜度分析：準確分析時間和空間復雜度
  4. 代碼實現：能夠快速寫出正確的代碼
  5. 邊界處理：考慮各種邊界情況

11.3 最終建議

  1. 多練習：通過大量練習加深理解
  2. 畫圖輔助：用圖形化方式理解算法過程
  3. 代碼調試：通過調試驗證算法的正確性
  4. 舉一反三：學會將 Floyd 算法應用到其他問題
  5. 總結歸納：定期總結學習心得和經驗

總結：
環形鏈表 II 是一道經典的鏈表算法題，Floyd 快慢指針法是最優解。掌握這道題不僅能提高鏈表操作能力，還能學習到重要的算法思想。建議從簡單的 HashSet 方法開始，逐步理解 Floyd 算法的數學原理，最終能夠熟練應用到各種相關問題中。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/86438.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/86438.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/86438.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

安寶特科技丨Pixee Medical產品獲FDA認證 AR技術賦能骨科手術智能化

安寶特科技丨Pixee Medical產品獲FDA認證 AR技術賦能骨科手術智能化

法國醫療科技企業Pixee Medical宣布&#xff0c;其研發的智能骨科手術導航系統 Knee NexSight 解決方案正式通過美國食品藥品監督管理局&#xff08;FDA&#xff09;510(k)認證&#xff0c;標志著增強現實&#xff08;AR&#xff09;技術在醫療領域的商業化應用邁出關鍵一步。 …
閱讀更多...
操作系統的概念，功能和目標

操作系統的概念，功能和目標

小懶來了&#xff01; 操作系統學習正式開始&#xff0c;day1是小懶O&#xff01; Using blogs to organize and understand knowledge is a good way, lets learn, operating systems Chapter 1,Lets look at it &#xff08;一&#xff09;預備知識 一.什么是接口 1.假設我…
閱讀更多...
STM32使用水位傳感器

STM32使用水位傳感器

1.1 介紹&#xff1a; 水位傳感器專為水深檢測而設計&#xff0c;可廣泛用于感應降雨&#xff0c;水位&#xff0c;甚至液體泄漏。當將水位傳感器放入水中時&#xff0c;水位沒過銅線越多模擬值越大&#xff0c;讀取水深傳感器模塊的模擬值&#xff0c;在串口打印出來&#xf…
閱讀更多...
Spring事務傳播機制有哪些？

Spring事務傳播機制有哪些？

導語&#xff1a; Spring事務傳播機制是后端面試中的必考知識點&#xff0c;特別容易出現在“項目細節挖掘”階段。面試官通過它來判斷你是否真正理解事務控制的本質與異常傳播機制。本文將從實戰與源碼角度出發&#xff0c;全面剖析Spring事務傳播機制&#xff0c;幫助你答得有…
閱讀更多...
相機Camera日志實例分析之一：相機Camx【前置慢動作分辨率切換720P、1080P錄制】單幀流程日志詳解

相機Camera日志實例分析之一：相機Camx【前置慢動作分辨率切換720P、1080P錄制】單幀流程日志詳解

【關注我&#xff0c;后續持續新增專題博文&#xff0c;謝謝&#xff01;&#xff01;&#xff01;】 上一篇我們講了&#xff1a; 這一篇我們開始講&#xff1a; 目錄 一、場景操作步驟 二、日志基礎關鍵字分級如下 三、場景日志如下&#xff1a; 一、場景操作步驟 1、打…
閱讀更多...
OpenHarmony標準系統-HDF框架之I2C驅動開發

OpenHarmony標準系統-HDF框架之I2C驅動開發

文章目錄 引言I2C基礎知識概念和特性協議&#xff0c;四種信號組合 I2C調試手段硬件軟件 HDF框架下的I2C設備驅動案例描述驅動Dispatch驅動讀寫 總結 引言 I2C基礎知識 概念和特性 集成電路總線&#xff0c;由串網12C(1C、12C、Inter-Integrated Circuit BUS)行數據線SDA和串…
閱讀更多...
Ubuntu系統下交叉編譯openssl

Ubuntu系統下交叉編譯openssl

一、參考資料 OpenSSL&&libcurl庫的交叉編譯 - hesetone - 博客園 二、準備工作 1. 編譯環境 宿主機&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉編譯器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 設置交叉編譯工具鏈 在交叉編譯之前&#x…
閱讀更多...
數據庫優化實戰分享：高頻場景下的性能調優技巧與案例解析

數據庫優化實戰分享：高頻場景下的性能調優技巧與案例解析

在實際開發與生產運維中&#xff0c;數據庫的性能瓶頸往往是影響系統響應速度和用戶體驗的關鍵因素。尤其是在高并發訪問、海量數據處理、復雜查詢邏輯等高頻場景下&#xff0c;數據庫優化不僅僅是“錦上添花”&#xff0c;更是“雪中送炭”。本篇博文將結合實際項目經驗&#…
閱讀更多...
Python importlib 動態加載

Python importlib 動態加載

文章目錄 1. importlib 庫 概述2. 導入模塊&#xff08;import_module()&#xff09;2.1. 導入已安裝的模塊2.2. 導入子模塊2.3 通過字符串變量導入模塊 3. 重新加載模塊&#xff08;reload()&#xff09;4. 檢查模塊是否存在&#xff08;find_spec()&#xff09;5. 獲取模塊路…
閱讀更多...
(1-6-4) Java IO流實現文件的讀取與寫入

(1-6-4) Java IO流實現文件的讀取與寫入

目錄 0.前述概要 1. File類 1.1 概述 1.2 File的重要方法 1.3 java.io 1.3.1 四種抽象類 1.3.2 流 1.3.3 其他常用 I/O 流 2. 字節輸入流&#xff08;InputSteam&#xff09; 2.1 關系類圖 2.2 應用實現 3. 字節輸出流&#xff08;OutputStream&#xff09; 3.1 …
閱讀更多...
【Proteus仿真】【32單片機-A010】步進電機控制系統設計

【Proteus仿真】【32單片機-A010】步進電機控制系統設計

目錄 一、主要功能 二、使用步驟 三、硬件資源 四、軟件設計 五、實驗現象 聯系作者 一、主要功能 1、LCD顯示當前擋位、方向等&#xff1b; 2、按鍵控制步進電機擋位、方向等。 二、使用步驟 系統運行后&#xff0c;LCD1602顯示當前擋位、方向&#xff1b; 通過按鍵…
閱讀更多...
DeepSeek-R1-0528-Qwen3-8B為底座微調領域大模型準備:制作領域專用數據集

DeepSeek-R1-0528-Qwen3-8B為底座微調領域大模型準備:制作領域專用數據集

前言 想要微調領域大模型，數據的準備是必不可少的。然而微調大模型需要的數據極多，這樣花費很多人力和準備。有沒有方便又高效的方法？一下子就可以準備大量的領域專用數據集呢？ 制作領域專用數據集 這里制作的數據集格式為使用的aphaca格式的 1.啟動vllm服務 python -m…
閱讀更多...
WEB3全棧開發——面試專業技能點P6后端框架 / 微服務設計

WEB3全棧開發——面試專業技能點P6后端框架 / 微服務設計

一、Express Express是國內大部分公司重點問的。我在本文最后&#xff0c;單獨講解了Express框架。 概念介紹 Express 是基于 Node.js 平臺的極簡、靈活且廣泛使用的 Web 應用框架。它提供了一系列強大的功能&#xff0c;用于構建單頁、多頁及混合型的 Web 應用程序和 API 服…
閱讀更多...
游戲開發中的CI/CD優化案例：知名游戲公司Gearbox使用TeamCity簡化CI/CD流程

游戲開發中的CI/CD優化案例：知名游戲公司Gearbox使用TeamCity簡化CI/CD流程

案例背景 關于Gearbox&#xff1a; Gearbox 是一家美國電子游戲公司&#xff0c;總部位于德克薩斯州弗里斯科&#xff0c;靠近達拉斯。Gearbox 成立于1999年&#xff0c;推出過多款史上最具代表性的視頻游戲&#xff0c;包括《半衰期》、《戰火兄弟連》以及《無主之地》。 團隊…
閱讀更多...
視覺slam--三維剛體運動

視覺slam--三維剛體運動

線性代數 外積與矩陣乘法的等價性 歐拉角的奇異性--萬向死鎖 現象 第二個軸旋轉度&#xff0c;會導致第三個旋轉軸和惡原始坐標軸的第一個旋轉軸重合&#xff0c;導致第一次旋轉與第三次旋轉都使用了同一個軸進行旋轉&#xff0c;也就是本質上旋轉三次&#xff0c;但是只在兩個…
閱讀更多...
內窺鏡檢查中基于提示的息肉分割|文獻速遞-深度學習醫療AI最新文獻

內窺鏡檢查中基于提示的息肉分割|文獻速遞-深度學習醫療AI最新文獻

Title 題目 Prompt-based polyp segmentation during endoscopy 內窺鏡檢查中基于提示的息肉分割 01 文獻速遞介紹 以下是對這段英文內容的中文翻譯&#xff1a; ### 胃腸道癌癥的發病率呈上升趨勢&#xff0c;且有年輕化傾向&#xff08;Bray等人&#xff0c;2018&#x…
閱讀更多...
CppCon 2015 學習:REFLECTION TECHNIQUES IN C++

CppCon 2015 學習:REFLECTION TECHNIQUES IN C++

關于 Reflection&#xff08;反射&#xff09; 這個概念&#xff0c;總結一下&#xff1a; Reflection&#xff08;反射&#xff09;是什么&#xff1f; 反射是對類型的自我檢查能力&#xff08;Introspection&#xff09; 可以查看類的成員變量、成員函數等信息。反射允許枚…
閱讀更多...
R語言速釋制劑QBD解決方案之一

R語言速釋制劑QBD解決方案之一

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一個處方的R語言解決方案。 第一個處方研究評估原料藥粒徑分布、MCC/Lactose比例、崩解劑用量對制劑CQAs的影響。 第二處方研究用于理解顆粒外加硬脂酸鎂和滑石粉對片劑質量和可生產…
閱讀更多...
“詳規一張圖”——新加坡土地利用數據

“詳規一張圖”——新加坡土地利用數據

在城市規劃和土地管理領域&#xff0c;精確且詳盡的空間數據是進行有效決策的基石。隨著地理信息系統&#xff08;GIS&#xff09;技術的發展&#xff0c;我們能夠以前所未有的精度和細節來捕捉、分析和展示土地利用信息。這不僅提升了數據的質量和可靠性&#xff0c;還使得城市…
閱讀更多...
LabVIEW雙光子成像系統技術

LabVIEW雙光子成像系統技術

雙光子成像技術的核心特性 雙光子成像通過雙低能量光子協同激發機制&#xff0c;展現出顯著的技術優勢&#xff1a; 深層組織穿透能力&#xff1a;適用于活體組織深度成像 高分辨率觀測性能&#xff1a;滿足微觀結構的精細研究需求 低光毒性特點&#xff1a;減少對樣本的損傷…
閱讀更多...
最新文章

Copyright @ 2022~2023