手帐 Blog

主题

复盘 · LC 141 环形链表 ​

题目 ​

题意 ​

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

边界：空链、单节点无环、尾接自己、环在中部。

涉及算法 ​

标签一句话
哈希表 / Set走过的节点放进集合，再次出现即有环
快慢指针（Floyd）slow 一步、fast 两步，能相遇则有环

教程对照：13 · 链表进阶；快慢模板也见 06 · 同向双指针与快慢指针。

评价我的解法 ​

我的代码（摘自 141-环形链表/index.js）：

javascript
var hasCycle = function (head) {
  const nodeList = new Set();
  let isHasCycle = false;
  while (true) {
    if (!head) {
      break;
    }
    if (nodeList.has(head)) {
      isHasCycle = true;
      break;
    }
    nodeList.add(head);
    head = head.next;
  }
  return isHasCycle;
};

判断正确：用节点引用进 Set（不是 val），再次命中即环——和 7/20 相交链表同一套「引用判等」直觉。

  • 时间 O(n)，空间 O(n)。
  • 优点：边界清晰，空链自然 false。
  • 可改进：while (true) + 中间布尔可压成 while (head) { ... return true } / 末尾 return false；进阶常考 O(1) 空间 快慢指针。

最佳题解 ​

Floyd 快慢指针：

javascript
/**
 * @param {ListNode} head
 * @return {boolean}
 */
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 先到末尾。

面试可先讲 Set 保正确，再主动升级到快慢指针。

关联题目 ​

题为何相关
142. 环形链表 II找环入口；快慢 + 再从头对齐
160. 相交链表同属「相遇 / 对齐路程」家族
202. 快乐数快慢指针判「环」的非链表版

一句话带走 ​

环形链表：Set 看节点是否重访；面试加一句——快两步慢一步，相遇即有环。