手帐 Blog

主题

复盘 · LC 141 环形链表（二刷） ​

题目 ​

题意 ​

给定链表头 head，判断是否存在环：某个节点的 next 能再次回到先前出现过的节点。有环返回 true，否则 false。

  • 空链、单节点无环都是 false。
  • 进阶：尽量 O(1) 额外空间。

边界：无环走到 null；环在尾部；整条都是环；单节点自环。

涉及算法 ​

标签一句话
哈希 / 打标走过的节点放进 Set（或改节点字段），再遇即有环
快慢指针（Floyd）slow 走一步、fast 走两步，能相遇则有环

教程对照：13 · 链表进阶（环检测、相交、合并）。

评价我的解法 ​

相对 7/22 首刷，今天仍是「走过打标」思路，能 AC，但还没升到快慢指针模板。

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

javascript
var hasCycle = function (head) {
  if (!head) {
    return false;
  }
  if (!head && !head.next) {
    return false;
  }
  let cur = head,
    pre = null,
    next = null;
  let isCycle = false;
  while (true) {
    if (cur && cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    if (cur.isVisit) {
      isCycle = true;
      break;
    }
    cur.isVisit = true;
    pre = cur;
    cur = next;
    if (!cur) {
      break;
    }
  }
  return isCycle;
};

主流程能过（提交 29/29）：靠给节点挂 isVisit 标记，再遇即判环。

  • 时间 O(n)，空间 名义 O(1) 字段、实质仍是 O(n) 额外信息，且改坏了输入结构——面试常被追问。
  • 糙点 / 坑：
    1. 第二行 if (!head && !head.next)：前面已 !head 返回，这里恒为假，是死代码；本意多半是 !head || !head.next。
    2. pre 从未参与判定，属于反转链表模板残留。
    3. 同系列其它题的 while (true) + 手动取 next，可收成 while (cur)。
    4. 耗时/内存都偏后（约 22% / 14%）——打标法的典型代价。

小结：正确性没问题，但二刷目标应是 Floyd 快慢指针；今天还停在「哈希变体」。

最佳题解 ​

快慢指针：

javascript
/**
 * @param {ListNode} head
 * @return {boolean}
 */
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;
};

或更常见的「同起点再起步」写法：

javascript
var hasCycle = function (head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
};
  • 时间 O(n)，空间 O(1)，不改节点。
  • 直觉：环上相对速度差 1，终会相遇；无环则 fast 先撞 null。

关联题目 ​

题为何相关
142. 环形链表 II找环入口：相遇后再从头与慢指针同步
160. 相交链表另一类「指针对齐 / 相遇」
287. 寻找重复数数组当「链表」跑 Floyd

一句话带走 ​

环形链表：能 AC 的打标不够面试；口述 慢一步快两步，相遇有环，撞 null 无环。