題解：環形鏈表

在這道題目中，我們需要判斷一個鏈表是否存在環。環的定義是鏈表的某個節點可以通過連續跟蹤 next 指針回到自身。如果存在這樣的環，那么就返回 true，否則返回 false。

方法一：使用哈希集合 (HashSet)

思路：

• 遍歷鏈表，使用一個哈希集合 (HashSet) 存儲每個訪問過的節點。
• 每遍歷一個節點時，檢查該節點是否已經存在于集合中。如果存在，說明鏈表中存在環；如果不存在，則將該節點加入集合中。
• 如果遍歷完整個鏈表都沒有發現重復節點，說明鏈表中不存在環。

代碼實現：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode curr = head;
        while (curr != null) {
            // 如果當前節點已經在集合中，說明有環
            if (!set.add(curr)) {
                return true;
            }
            curr = curr.next; // 繼續遍歷下一個節點
        }
        return false; // 如果遍歷到鏈表末尾沒有發現環
    }
}

復雜度分析：

• 時間復雜度：O(n)，其中 n 是鏈表的節點數。我們每個節點只遍歷一次。
• 空間復雜度：O(n)，需要額外的哈希集合來存儲每個訪問的節點。

過程解析：

1. 初始化一個空的 HashSet。
2. 從頭節點開始遍歷鏈表，每遇到一個節點，檢查它是否在 HashSet 中。如果在，說明有環，返回 true；否則，將該節點加入集合，繼續遍歷下一個節點。
3. 如果遍歷到了鏈表的末尾（即 curr == null），說明鏈表沒有環，返回 false。

方法二：快慢指針 (Floyd 判圈算法)

思路：

• 使用兩個指針：一個快指針 (fast)，一個慢指針 (slow)。
• 快指針每次走兩步，慢指針每次走一步。
• 如果鏈表中沒有環，快指針會在遍歷完鏈表時到達 null。
• 如果鏈表中有環，快指針會最終追上慢指針，兩者會相遇。

代碼實現：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head; // 慢指針
        ListNode fast = head.next; // 快指針

        // 快慢指針相遇說明有環
        while (fast != slow) {
            if (fast == null || fast.next == null) return false; // 快指針提前到達終點，說明沒有環
            fast = fast.next.next; // 快指針走兩步
            slow = slow.next; // 慢指針走一步
        }

        return true; // 兩個指針相遇，說明有環
    }
}

復雜度分析：

• 時間復雜度：O(n)，其中 n 是鏈表的節點數。最壞情況下，快指針和慢指針遍歷鏈表中的每個節點。
• 空間復雜度：O(1)，我們只用了常數級別的額外空間。

過程解析：

1. 快指針 fast 每次走兩步，慢指針 slow 每次走一步。
2. 如果鏈表中有環，快指針最終會追上慢指針，這時返回 true。
3. 如果快指針在遍歷過程中到達了 null，則鏈表沒有環，返回 false。

方法比較：

1. 哈希集合法使用了額外的存儲空間，但思路簡單易懂，適合初學者。
2. 快慢指針法雖然稍微復雜一點，但它不需要額外的空間，能夠以 O(1) 的空間復雜度解決問題，在面試中常被要求使用這種方法。

這道題目考察了鏈表的基本操作以及快慢指針的應用，通過分析鏈表的結構，可以更好地掌握鏈表與指針的使用。