Linked List Cycle（环形链表）

题目 / Problem

中文： 给定一个链表的头节点 head，判断链表中是否存在环。

如果从链表中的某个节点出发，持续沿着 next 指针移动，最终能够再次到达已经访问过的节点，则该链表存在环。

在测试数据中，pos 表示链表尾节点的 next 指针连接到的节点下标。需要注意，pos 只是用于描述测试数据，并不会作为参数传入函数。

如果链表中存在环，返回 true；否则返回 false。

English: Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if some node can be reached again by continuously following the next pointer. Internally, pos denotes the index of the node to which the tail's next pointer is connected. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

示例 / Examples

Example 1

Input:  head = [3,2,0,-4], pos = 1
Output: true

3 → 2 → 0 → -4
    ↑         │
    └─────────┘

尾节点 -4 连接到下标为 1 的节点 2，因此链表中存在环。
The tail node -4 connects to node 2 at index 1, so the list contains a cycle.

Example 2

Input:  head = [1,2], pos = 0
Output: true

1 → 2
↑   │
└───┘

尾节点 2 连接回下标为 0 的节点 1，因此链表中存在环。
The tail node 2 connects back to node 1 at index 0, so the list contains a cycle.

Example 3

Input:  head = [1], pos = -1
Output: false

pos = -1 表示尾节点没有连接到链表中的其他节点，因此不存在环。
pos = -1 means the tail does not connect to another node in the list, so there is no cycle.

约束 / Constraints

• 链表中的节点数在 [0, 10⁴] 范围内。
  The number of nodes in the list is in the range [0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• pos 为 -1 或链表中的有效下标。
  pos is -1 or a valid index in the linked list.

进阶 / Follow-up

能否只使用 O(1) 的额外空间解决此问题？
Can you solve the problem using O(1) extra memory?

解题思路：快慢指针 / Approach: Fast and Slow Pointers

使用 Floyd 判圈算法，同时维护两个从头节点出发的指针：
Use Floyd's cycle detection algorithm with two pointers starting at the head:

• slow 每次向后移动一个节点。
  slow moves forward by one node at a time.
• fast 每次向后移动两个节点。
  fast moves forward by two nodes at a time.

可能出现两种情况：
There are two possible outcomes:

1. 如果链表没有环，fast 或 fast.next 最终会变为 null，返回 false。
   If the list has no cycle, fast or fast.next eventually becomes null, so return false.
2. 如果链表存在环，两个指针进入环后，fast 每轮会相对 slow 靠近一个节点，最终必然相遇，返回 true。
   If the list contains a cycle, once both pointers enter it, fast gains one node on slow per iteration, so they must eventually meet; return true.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *   this.val = val;
 *   this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

比较时必须使用 slow === fast 判断两个指针是否指向同一个节点对象，而不是比较节点值。不同节点可能拥有相同的 val。
The comparison must use slow === fast to check whether both pointers reference the same node object. Different nodes may have the same val.

执行过程 / Walkthrough

以 head = [3,2,0,-4]、pos = 1 为例：
For head = [3,2,0,-4] and pos = 1:

3 → 2 → 0 → -4
    ↑         │
    └─────────┘

尽管表格使用节点值展示位置，代码实际比较的是节点引用。
Although the table uses values to show positions, the code compares node references.

为什么快慢指针一定会相遇？ / Why Must the Pointers Meet?

当两个指针都进入环后，可以把环看成一条循环跑道。fast 每轮移动两步，slow 每轮移动一步，因此 fast 相对于 slow 每轮前进一个节点。
Once both pointers enter the cycle, treat it as a circular track. fast moves two steps per round while slow moves one, so fast advances by one node relative to slow each round.

由于环中的节点数有限，这个相对距离会不断缩小并最终变为 0，此时两个指针指向同一个节点。
Because the cycle contains a finite number of nodes, this relative distance eventually becomes 0, placing both pointers on the same node.

复杂度 / Complexity

设链表中共有 n 个不同节点。
Let the list contain n distinct nodes.

• 时间复杂度：O(n)。无环时最多遍历整条链表；有环时，两个指针会在进入环后的有限步内相遇。
  Time: O(n). Without a cycle, the list is traversed once; with a cycle, the pointers meet within a bounded number of steps after entering it.
• 空间复杂度：O(1)，只使用两个额外指针。
  Space: O(1), because only two extra pointers are used.

哈希集合解法 / Hash Set Approach

也可以使用 Set 保存已经访问过的节点。遍历过程中，如果再次遇到集合中的节点，说明存在环。
A Set can store previously visited nodes. Encountering a node already in the set means the list contains a cycle.

function hasCycleWithSet(head) {
  const visited = new Set();
  let current = head;

  while (current !== null) {
    if (visited.has(current)) {
      return true;
    }

    visited.add(current);
    current = current.next;
  }

  return false;
}

• 时间复杂度 / Time: O(n)
• 空间复杂度 / Space: O(n)，集合最多保存所有节点。
  The set may store every node.

快慢指针解法不需要保存访问记录，因此满足进阶要求的 O(1) 额外空间。
The fast-and-slow pointer solution stores no visit history, satisfying the O(1) extra-space follow-up.

易错点 / Common Pitfalls

• pos 不会传入 hasCycle，不能依赖它判断是否有环。
  pos is not passed to hasCycle, so the solution cannot rely on it.
• 循环条件必须同时检查 fast 和 fast.next，避免访问 null.next。
  Check both fast and fast.next in the loop condition to avoid accessing null.next.
• 应比较节点引用 slow === fast，而不是节点值。
  Compare node references with slow === fast, not node values.
• 空链表和只有一个无自环节点的链表都应返回 false。
  Return false for an empty list and for a single node without a self-cycle.
• 不要尝试通过修改节点值标记访问状态，这可能破坏输入链表。
  Do not mark visits by modifying node values, because that can corrupt the input list.