BFE.devAI解答 - JavaScript 代码题
100. 检测链表中是否有环

方法一：快慢指针

使用快慢指针，快指针每次走两步，慢指针每次走一步，如果存在环，快指针一定会在某个时刻追上慢指针。

时间复杂度 O(n)，空间复杂度 O(1)。

代码如下：

function hasCycle(head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      return true;
    }
  }
  return false;
}

方法二：标记法

使用一个标记变量标记每个节点是否被访问过，如果某个节点被重复访问，则说明存在环。

时间复杂度 O(n)，空间复杂度 O(n)。

代码如下：

function hasCycle(head) {
  let curr = head;
  while (curr) {
    if (curr.visited) {
      return true;
    } else {
      curr.visited = true;
      curr = curr.next;
    }
  }
  return false;
}

方法三：哈希表

使用哈希表存储每个节点，如果某个节点被重复访问，则说明存在环。

时间复杂度 O(n)，空间复杂度 O(n)。

代码如下：

function hasCycle(head) {
  const map = new Map();
  let curr = head;
  while (curr) {
    if (map.has(curr)) {
      return true;
    } else {
      map.set(curr, true);
      curr = curr.next;
    }
  }
  return false;
}

总结：

快慢指针是最优解，时间空间复杂度均最优。标记法和哈希表方法都是时间复杂度 O(n)，空间复杂度 O(n)，但是因为需要额外的空间存储标记或哈希表，所以不如快慢指针方法。