检测链表环

问题

给定一个链表，判断链表中是否存在环。如果存在环，返回 true；否则返回 false。

解答

定义链表节点

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

方法一：哈希表

function hasCycle(head) {
  // 用 Set 存储访问过的节点
  const visited = new Set();
  let current = head;

  while (current !== null) {
    // 如果当前节点已访问过，说明有环
    if (visited.has(current)) {
      return true;
    }
    visited.add(current);
    current = current.next;
  }

  return false;
}

方法二：快慢指针（Floyd 判圈算法）

function hasCycle(head) {
  if (head === null || head.next === null) {
    return false;
  }

  let slow = head; // 慢指针，每次走一步
  let fast = head; // 快指针，每次走两步

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    // 快慢指针相遇，说明有环
    if (slow === fast) {
      return true;
    }
  }

  return false;
}

测试代码

// 创建有环链表：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

// 创建无环链表：1 -> 2 -> 3
const a = new ListNode(1);
const b = new ListNode(2);
const c = new ListNode(3);
a.next = b;
b.next = c;

console.log(hasCycle(a)); // false

关键点

• 哈希表法：时间 O(n)，空间 O(n)，用 Set 记录访问过的节点
• 快慢指针法：时间 O(n)，空间 O(1)，快指针每次走两步，慢指针每次走一步
• 相遇原理：如果有环，快指针一定会追上慢指针；如果无环，快指针会先到达 null
• 边界处理：空链表或只有一个节点且无环时直接返回 false