环形链表（判断是否有环并返回环起点）

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

问题一:判断链表是否有环(LeetCode 141)

给你一个链表的头节点 head,判断链表中是否存在环。如果链表中某个节点可以通过 next 指针再次到达,则链表中存在环。

输入：head = [3,2,0,-4]，tail 连接到索引 1 的节点
输出：true       // -4 的 next 指回了值为 2 的节点，成环

问题二:返回环的起始节点(LeetCode 142)

在存在环的情况下,返回链表开始入环的第一个节点;若无环,返回 null。

输入：head = [3,2,0,-4]，tail 连接到索引 1
输出：值为 2 的节点      // 环的入口

环形链表最迷惑的地方:你不能靠"走到 null"来判断结束——有环的链表永远走不到 null,会无限循环。所以我们需要更聪明的判定手段。

思路拆解

暴力解法:哈希表记录访问过的节点

最直觉的想法:一边遍历一边把走过的节点存进哈希集合。若某个节点再次出现,说明成环,它就是环的入口;若走到 null,说明无环。

点击展开哈希表解法（好懂，但需 O(n) 空间）

// 记录访问过的节点，重复出现即为环入口
function detectCycle(head) {
  const seen = new Set();
  let node = head;
  while (node) {
    if (seen.has(node)) return node; // 第一个重复的节点就是环入口
    seen.add(node);
    node = node.next;
  }
  return null; // 走到 null，无环
}

哈希表解法有什么不足？

它正确且直观,时间 ,但需要额外 空间存所有节点引用。面试官几乎必然追问:"能否做到 空间?"——这就引出了 Floyd 判圈算法(龟兔赛跑)。

最优解法:Floyd 快慢指针(判环)

核心思想:让 slow 一次走一步、fast 一次走两步。

为什么快慢指针能判环？

• 无环:fast 会先到达 null,循环结束,返回无环;
• 有环:两个指针都会进入环。此后 fast 相对 slow 每轮多走一步,相当于在环上不断"追赶",两者距离每轮缩小 1,最终必然相遇(不会跳过,因为差距是连续减 1 的)。

一句话:跑道上快的人早晚会套圈追上慢的人。 相遇即证明有环。

最优解法:定位环起点(数学推导)

判环后,如何找到入环的第一个节点?这里有一个优雅的结论。设:

• = 头节点到环入口的距离;
• = 环入口到相遇点的距离;
• = 相遇点绕回环入口的距离(即环长 )。

环起点的推导

相遇时,slow 走了 ,fast 走了 ( 圈)。由于 fast 速度是 slow 两倍,路程也是两倍:

化简得:

即 。这说明:从头节点走 步,和从相遇点走 步(可能多绕几圈),会同时到达环入口!

所以:相遇后,让一个指针回到 head,另一个留在相遇点,两者都每次走一步,再次相遇的地方就是环入口。

交互式动画演示

下面用样例链表 3 → 2 → 0 → -4(尾节点 -4 指回值为 2 的节点)演示 Floyd 快慢指针的完整过程:先快慢相遇判环,再让一指针回到头部、同速前进定位环入口:

步骤 1 / 6初始化

slow (慢·1步)fast (快·2步)ptr (回头指针)环入口

初始化：slow 与 fast 都从头节点 3 出发。slow 每次走 1 步，fast 每次走 2 步。

完整代码(JavaScript)

问题一:判断是否有环

高亮行为快慢指针推进与相遇判定。

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

  while (fast && fast.next) {
    slow = slow.next;        // 慢指针走一步
    fast = fast.next.next;   // 快指针走两步
    if (slow === fast) return true; // 相遇即有环
  }

  return false; // fast 到达 null，无环
}

问题二:返回环的起始节点

高亮行为"相遇后一指针回头、同速再相遇"的核心。

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

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // 相遇！开始第二阶段：定位环入口
      let ptr = head;
      // ptr 从头出发，slow 留在相遇点，同速前进
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr; // 相遇处即环入口
    }
  }

  return null; // 无环
}

复杂度分析

设链表节点总数为 。

解法	时间复杂度	空间复杂度	说明
哈希表			存储所有访问过的节点引用
Floyd 判环(141)			快慢指针,相遇即有环
Floyd 找入口(142)			判环 + 第二阶段同速追赶

时间为何仍是 ?第一阶段 slow 至多走 步就会相遇;第二阶段两指针至多再走一个环长。总计线性。

边界与易错点

常见踩坑

1. 循环条件必须是 fast && fast.next:因为 fast 每次跳两步,要同时保证 fast 和 fast.next 都非空,否则 fast.next.next 会报空指针错误。
2. 判环阶段快慢指针的起点:本文让两者都从 head 出发。此时第一步就移动再比较(先 slow = slow.next 再判等),避免初始都在 head 时被误判为"相遇"。
3. 找入口时必须"同速":第二阶段两个指针都是每次一步,不要再让某个走两步——推导公式依赖的正是同速。
4. 相遇点不是环入口:很多人误以为快慢相遇的地方就是环起点,其实不是。必须做第二阶段,让一个指针回到 head 再同速追。
5. 无环情况:fast 或 fast.next 为 null 时循环退出,返回 false / null,别忘了处理。
6. 单节点自环:head.next === head 也算环,快慢指针写法天然覆盖。

简易解题思路(记忆口诀)

一句话记忆:「龟兔赛跑先判环,兔慢回头找入口」

把它想象成操场上的龟兔赛跑:

• 兔子(fast)一步两格,乌龟(slow)一步一格:如果跑道是环形的,兔子早晚会套圈追上乌龟——它们相遇,就证明"有环";如果兔子跑到了尽头(null),说明是直路,"无环"。
• 找环的入口:相遇后,把兔子拉回起点(head)、降速成一步一格,乌龟留在相遇处也一步一格,两人同速走,再次碰面的地方就是环的入口。这背后是等式 在撑腰。

两句话口诀:

1. 判环:快慢跑,相遇即有环,快到头即无环;
2. 找口:相遇后一个回头,同速再走,碰面即入口。

记住核心画面:"快慢相遇证明有环 → 一个回头、同速再走 → 二次相遇就是入口。"