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)，但是因为需要额外的空间存储标记或哈希表，所以不如快慢指针方法。