1. 對應力扣題目連接

• 環形鏈表 II

2. 實現思路

a. 鏈表圖示：

b. 檢測鏈表中是否存在環，即：會相交

思路：

• 使用 Floyd 的龜兔賽跑算法（Floyd’s Tortoise and Hare algorithm），即快慢指針法，可以有效解決此問題。

方案：

• 初始化兩個指針，慢指針 (slow) 每次走一步，快指針 (fast) 每次走兩步。
  如果鏈表中存在環，快指針和慢指針最終會在環內相遇。
  如果鏈表無環，快指針會先到達鏈表末端。如上圖示。

c. 找到環的起點，即：環形入口點

思路：

• 因為環會相交，所有里程數一定相等，而快慢指針的速度差為2:1；
• 所以：快慢總的里程等式為（n代表快指針的圈數）：（x+y）* 2 = x+y + n(y+z)
• 推算：
• x+y = n(y+z)
• x = n(y+z) -y
• x = (n-1)(y+z) +z
• 如：n=1；則 x=z

方案：

• 當快慢指針在環內相遇時，將其中一個指針重置到鏈表頭部。
• 兩個指針每次都只走一步，當它們再次相遇時，相遇的節點即為環的起點。

3. 實現案例代碼

public class CircularListIiTwo {public static void main(String[] args) {// 示例鏈表：[3,2,0,-4]，尾部連接到索引 1ListNode head = new ListNode(3);ListNode node1 = new ListNode(2);ListNode node2 = new ListNode(0);ListNode node3 = new ListNode(-4);head.next = node1;node1.next = node2;node2.next = node3;node3.next = node1;  // 構成環ListNode cycleNode = detectCycle(head);if (cycleNode != null) {System.out.println("Cycle starts at node with value: " + cycleNode.val);} else {System.out.println("No cycle");}}public static 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) {ListNode ptr = head;// 找到環的起點while (ptr != slow) {ptr = ptr.next;slow = slow.next;}return ptr;}}// 無環return null;}
}class ListNode {public int val;public ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}