您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

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

編輯：Java 相關知識

「判斷單鏈表是否有環」是微軟、Google 等大廠高頻面試題，也是 Floyd 判圈算法（快慢指針）的經典應用。本文從數學原理、代碼實現、邊界條件、擴展問題（找環入口、計算環長度）全維度講解。

一、核心思想：快慢指針

慢指針 每次移動 1 步
快指針 每次移動 2 步
無環：快指針先到達 null，返回 false
有環：快指針在環內追上慢指針（相遇），返回 true

數學證明（有環必相遇）

設環外長度 a，環長度 b。慢指針進環時走過 a 步，快指針走過 2a 步，已在環內領先慢指針 a % b 步。此後每輪快指針相對慢指針縮短 1 步距離，最多 b 輪必相遇。相遇點必在環內。

二、標準實現代碼

public class LinkedListCycleDetector {

    /** 單鏈表節點 */
    static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    /**
     * 判斷鏈表是否有環
     * @param head 鏈表頭節點
     * @return true 有環，false 無環
     */
    public static <T> boolean hasCycle(Node<T> head) {
        if (head == null || head.next == null) return false;

        Node<T> slow = head;
        Node<T> fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;          // 1 步
            fast = fast.next.next;     // 2 步
            if (slow == fast) return true; // 相遇 → 有環
        }
        return false; // fast 到達末尾 → 無環
    }

    // --- 測試用例 ---
    public static void main(String[] args) {
        // 無環鏈表
        Node<Integer> head1 = new Node<>(1);
        head1.next = new Node<>(2);
        head1.next.next = new Node<>(3);
        System.out.println("無環: " + hasCycle(head1)); // false

        // 有環鏈表：3 -> 2 形成環
        Node<Integer> head2 = new Node<>(1);
        Node<Integer> n2 = new Node<>(2);
        Node<Integer> n3 = new Node<>(3);
        head2.next = n2;
        n2.next = n3;
        n3.next = n2; // 環入口在 n2
        System.out.println("有環: " + hasCycle(head2)); // true

        // 單節點自環
        Node<Integer> selfLoop = new Node<>(99);
        selfLoop.next = selfLoop;
        System.out.println("自環: " + hasCycle(selfLoop)); // true
    }
}

三、進階擴展：環的入口節點與環長度

1. 找環入口

快慢指針相遇後，將其中一指針重置為 head，兩指針同速（各 1 步）前進，再次相遇點即為環入口。

public static <T> Node<T> detectCycleEntry(Node<T> head) {
    Node<T> slow = head, 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; // 無環

    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow; // 入口節點
}

原理：設入口距頭 a，相遇點距入口 x，環長 b。相遇時慢指針走 a+x，快指針走 2(a+x)，差值 a+x = kb → a = kb - x。從頭與相遇點同速走，恰在入口相遇。

2. 計算環長度

public static int cycleLength(Node<T> meetingNode) {
    int len = 1;
    Node<T> cur = meetingNode.next;
    while (cur != meetingNode) {
        len++;
        cur = cur.next;
    }
    return len;
}

四、完整測試鏈表工具類

public class SingleList<T> {
    private Node<T> head = new Node<>(null); // 哨兵節點
    private int size = 0;

    public void add(T value) {
        Node<T> node = new Node<>(value);
        node.next = head.next;
        head.next = node;
        size++;
    }

    /** 為測試創建環：尾節點指向第 index 個節點 (0-based) */
    public void createCycle(int index) {
        if (index < 0 || index >= size) return;
        Node<T> tail = head;
        while (tail.next != null) tail = tail.next;
        Node<T> target = head.next;
        for (int i = 0; i < index; i++) target = target.next;
        tail.next = target;
    }

    public Node<T> getHead() { return head.next; }
}