复盘 · LC 142 环形链表 II

题目

• 题号：LeetCode 142
• 名称：环形链表 II（Linked List Cycle II）
• 难度：Medium
• 链接：leetcode.cn/problems/linked-list-cycle-ii
• 今日代码：142-环形链表二/index.js

题意

给定链表头 head，若有环，返回环的入口节点（环开始的第一个节点）；无环返回 null。

• 与 141 的差别：不只判「有没有」，还要定位入口。
• 进阶：O(1) 额外空间。

边界：无环；环入口就是头；单节点自环；环在尾部。

涉及算法

标签	一句话
哈希表	走过的节点进 Set，第一次重复即入口
Floyd 找环入口	快慢相遇后，一指针回 head，两指针同步各走一步，再遇即入口

教程对照：13 · 链表进阶（环检测、找入口）。

评价我的解法

我的代码（摘自 142-环形链表二/index.js，不含本地测例）：

var detectCycle = function (head) {
  if (!head) {
    return null;
  }
  if (!head.next) {
    return null;
  }
  let fast = head;
  let slow = head;
  let firstNode = null;
  while (true) {
    if (fast.next && fast.next.next) {
      fast = fast.next.next;
    } else {
      break;
    }
    if (slow.next) {
      slow = slow.next;
    } else {
      break;
    }
    if (fast === slow) {
      firstNode = fast;
      break;
    }
  }
  if (!firstNode) {
    return null;
  }
  /* firstNode就是第一次相见的点 */
  fast = head;
  slow = firstNode;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
};

两阶段都对（提交 18/18）：先快慢找相遇点，再一头一相遇点同步走找入口——Floyd 结论用对了。

• 时间 O(n)，空间 O(1)。
• 优点：本地还搭了带环链测过，比只交题更扎实。
• 糙点：
  1. 第一阶段和 141 一样，while (true) 过碎，可读性差。
  2. firstNode 其实就是相遇时的 slow/fast，不必另存再赋值；第二阶段可直接 slow = head、fast 留在相遇点。
  3. 性能百分比偏低多半是写法冗余，算法量级没问题。

数学直觉（面试口述）：设头到入口 a、入口到相遇 b、环长 c。相遇时 2(a+b) = a+b+kc ⇒ a = kc - b，故从头与从相遇点同速走，必在入口相遇。

最佳题解

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  if (!head || !head.next) return null;
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
};

• 时间 O(n)，空间 O(1)。
• 为何更优：第一阶段循环条件干净；相遇后立刻进入第二阶段，少临时变量、少二次扫描结构。

关联题目

题	为何相关
141. 环形链表	本题第一阶段；今天同日三刷
160. 相交链表	「对齐路程再相遇」同一类证明
287. 寻找重复数	把数组下标当成 next，Floyd 找环入口

一句话带走

142：快慢相遇后，一指针回头部同步走——再遇就是环入口。