Day11-环形链表

🔗 LeetCode 141 - Linked List Cycle

📌 题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：true

---

💡 解题思路

使用快慢指针：

• 慢指针一次走一步；

• 快指针一次走两步；

• 如果链表有环，快慢指针最终会在某个节点相遇；

• 如果无环，快指针会先走到 null。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

---

✅ JavaScript 实现（快慢指针）

var hasCycle = function(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head.next;

    while (slow !== fast) {
        if (!fast || !fast.next) return false;
        slow = slow.next;
        fast = fast.next.next;
    }

    return true;
};

---

🧠 思考拓展

• 如果需要找出环的入口节点怎么做？（参见 LeetCode 142）
• 如果想统计环的长度呢？
• 使用哈希表是否也能解决？时间与空间复杂度如何变化？