环形链表检测

问题

给定一个链表，判断链表中是否有环。如果有环，找出环的入口节点。

解答

链表节点定义

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

判断是否有环

使用快慢指针（Floyd 判圈算法）：

function hasCycle(head) {
  if (!head || !head.next) return false;

  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;       // 慢指针走一步
    fast = fast.next.next;  // 快指针走两步

    // 相遇说明有环
    if (slow === fast) {
      return true;
    }
  }

  return false;
}

找到环的入口

function detectCycle(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) {
      // 第二阶段：找入口
      // 将 slow 重置到 head，两指针同速前进
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow; // 相遇点即为入口
    }
  }

  return null;
}

测试代码

// 创建有环链表: 1 -> 2 -> 3 -> 4 -> 2(回到节点2)
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // 形成环

console.log(hasCycle(node1));      // true
console.log(detectCycle(node1).val); // 2

为什么能找到入口？

设链表头到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c。

head ---(a)--- 入口 ---(b)--- 相遇点
                 ^              |
                 |-----(c)------|

• 相遇时，慢指针走了 a + b
• 快指针走了 a + b + n(b + c)，其中 n 是快指针多绕的圈数
• 因为快指针速度是慢指针的 2 倍：2(a + b) = a + b + n(b + c)
• 化简得：a = (n - 1)(b + c) + c

这意味着从 head 走 a 步，等于从相遇点走 c 步再绕若干圈，两者会在入口相遇。

关键点

• 快指针每次走 2 步，慢指针每次走 1 步，有环必相遇
• 时间复杂度 O(n)，空间复杂度 O(1)
• 找入口时，从 head 和相遇点同时出发，再次相遇即为入口
• 数学推导是理解算法的关键：a = (n-1)(b+c) + c