LeetCode 题解：141. 环形链表，JavaScript HashMap，详细注释

阅读更多系列文章请访问我的GitHub 博客



原题链接：https://leetcode-cn.com/problems/linked-list-cycle/



解题思路：



1. 遍历链表，同时用Map储存每个节点的指向。

2. 同时检查当前节点的指向是否已经在Map中储存，如果有则表示有两个节点指向了同一个节点，即为有环。

3. 代码中用Map实现，实际用Set也可以。

4. 此解法虽然可以成功判断是否存在环，但在142. 环形链表 II中，会因为无法正确判断环形链表只有1和2个元素时的指向而失败。



解法1：

```

/**

• Definition for singly-linked list.

• function ListNode(val) {

• this.val = val;

• this.next = null;

• }

*/



/**

• @param {ListNode} head

• @return {boolean}

*/

var hasCycle = function (head) {

// 如果节点不存在，则为false

if (!head) {

return false;

}



// 使用map存储遍历到的各个节点，此处也可以用Set

let map = new Map();

// 保存node存储

let node = head;



// 遍历链表，如果next指针指向为空，则表示链表结束时没有环

// 如果node.next无指向，则退出循环

while (node.next) {

// 如果当前map中已经保存了next指针的引用

// 也就是存在了一个重复的引用，两个next指针指向了同一个节点

// 此时表示有环存在

// 事实上map.get(undefined)和map.get(null)也会有值

// 但此时已经提前退出了while循环，因此不影响。

if (map.get(node.next)) {

return true;

}



// 保存next指针的引用

map.set(node.next, true);

// 储存下一个节点，继续遍历

node = node.next;

}



return false;

};



```



解法2：



```javascript []
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  // 使用map存储遍历到的各个节点，此处也可以用Set
  let set = new Set();
  // 保存node存储
  let node = head;

  while (node) {
    // 如果保存过node的指向，则表示有环
    if (set.has(node.next)) {
      return true;
    }

    // 在node.next存在时才保存其指向，避免保存node.next为null
    if (node.next) {
      set.add(node.next);
    }
    // 即使node.next无指向，还可以继续遍历，但下次会自动退出循环
    node = node.next;
  }

  return false;
};