141. 环形链表

LeetCode 原题链接

代码实现

方案一：哈希表

使用 Set 来存储访问过的节点，如果再次访问到已经访问过的节点，则说明链表存在环。

var hasCycle = function (head) {
  const list = new Set();
  let p = head;
  let pos = 0;
  while (p) {
    if (list.has(p)) return true;

    list.add(p);

    p = p.next;
  }
  return false;
};

方案二：快慢指针

使用两个指针，快指针每次移动两步，慢指针每次移动一步，如果链表存在环，则快慢指针最终会相遇。
如果快指针到达链表末尾，则说明链表没有环。
本质是利用追及问题的思想，创造速度差，快指针相当于追逐慢指针，如果存在环，快指针最终会追上慢指针。

var hasCycle = function (head) {
  // 如果链表为空，直接返回 false
  if (!head) 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;
};

为什么是“慢 1、快 2”而不是别的？
- 必须快于慢。如果两者速度一样（比如都 1），相对速度是 0，除非一开始重合，否则永远追不上。
- 相对速度要尽量简单稳定。选 1 和 2 时，相对速度是 1，推导最直接，实现也最不容易写错。
- 效率与安全性好。fast 每次要走两步，所以循环里检查 !fast || !fast.next 就足够安全。再快（比如 3 步）也能做，但要写更多空指针判断，可读性和实用性都变差，收益不明显。

ON THIS PAGE