經典算法：快慢指針法判斷單鏈表是否有環（Java 實現）

題目背景：微軟經典筆試題

「判斷單鏈表中是否存在環」是數據結構面試中的高頻經典題，曾作為微軟筆試真題。核心思路是快慢指針（Floyd 判圈算法），時間複雜度 O(N)，空間複雜度 O(1)，優於哈希表法的 O(N) 空間。

算法原理圖解

比喻：操場跑步
想象兩人在環形跑道上跑步：
- 慢指針 每次跨 1 步
- 快指針 每次跨 2 步

兩種結局：

1. 無環：快指針先跑到終點 (`null`)，相遇不可能發生。
2. 有環：快指針進入環後，在環內追趕慢指針。因速度差為 1 步/輪，必定相遇（相當於快指針套圈慢指針）。相遇點必在環內，不在入環前的鏈表段。

Java 核心代碼實現

public class LinkedListCycleDetector {

    /**
     * 判斷單鏈表是否有環
     * @param head 鏈表頭節點
     * @return true 存在環，false 無環
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // 快指針每次走兩步，需檢查 fast.next 防止空指針
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指針走一步
            fast = fast.next.next;  // 快指針走兩步
            
            if (slow == fast) {     // 相遇，說明有環
                return true;
            }
        }
        return false; // 快指針到達 null，無環
    }

    // 內部節點類
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

進階延伸：找到環的入口節點

若需定位環的入口（LeetCode 142），相遇後將任一指針重置為 head，兩指針改為同速（每次 1 步）前進，再次相遇點即為入口。數學證明：設入環前長度為 a，環長為 b，相遇時慢指針走過 s，快指針走過 2s。相遇點距入口 x，則 s = a + x，2s = a + n*b + x ⇒ s = n*b ⇒ a = n*b - x。即從 head 走 a 步，從相遇點走 (b-x) 步，同樣到達入口。

完整可運行測試代碼

public class Main {
    public static void main(String[] args) {
        // 構建無環鏈表: 1->2->3->4->5
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        
        // 構建有環鏈表: 1->2->3->4->5->3 (環入口為節點 3)
        ListNode head2 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head2.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3; // 形成環
        
        System.out.println("無環鏈表檢測: " + hasCycle(head1)); // false
        System.out.println("有環鏈表檢測: " + hasCycle(head2)); // true
    }
}

常見坑點提醒

• 循環條件：`while (fast != null && fast.next != null)` 缺一不可，否則 `fast.next.next` 會拋 NPE。
• 初始化：slow 和 fast 都從 head 開始，而非 head.next。
• 邊界情況：單節點自環 (`node.next = node`)、兩節點互環均能正確檢測。

總結

快慢指針法以極致的空間效率解決環檢測問題，是鏈表類面試題的「瑞士軍刀」。掌握其「相遇必在環內」、「入口定位數學模型」兩大核心結論，舉一反三可解決「鏈表中點查找」、「兩鏈表相交判斷」等變體問題。