写点什么

LeetCode 题解:141. 环形链表,JavaScript HashMap,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 07 月 16 日

阅读更多系列文章请访问我的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;
};



发布于: 2020 年 07 月 16 日阅读数: 56
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:141. 环形链表,JavaScript HashMap,详细注释