如何使用哈希表在单链表中查找循环？
如何使用哈希表在单链表中查找循环？
提问于 2020-06-03 04:58:43
我知道这是一个常见的问题，但我没有找到与我的算法不同的答案，但leetcode指出我的算法不起作用。如何使用哈希表来查找JS中的单链表中是否存在循环？我实现了以下算法：
var hasCycle = function(head) {
let node = head;
let table = {};
while(node) {
if(table[node.value]) {
return true;
}
else {
table[node.value] = true;
}
node = node.next;
}
return false;
};然而，在leetcode上，我的算法会一直工作到达到下面的测试用例：
Input: [1, 2], pos: -1其中[1, 2]是链表，pos是尾部指向的节点的位置。因为它是-1，所以尾部指向null，所以没有循环。
为什么leetcode说我的代码返回true？在我的while循环中，第一次迭代将table1设置为true。在第二次迭代中，table2被设置为true。然后我们退出while循环，因为node现在指向null，所以我的代码应该返回false。然而，leetcode说我的算法返回true。我哪里弄错了？
我知道乌龟和野兔算法，但我正在尝试理解哈希表方法来寻找循环。
回答 2
Stack Overflow用户
发布于 2020-06-03 05:05:54
本质上，您需要做的是遍历列表，看看哪个先出现？列表的末尾，或以前访问过的节点。您可以使用哈希表来记录您访问过的节点，虽然您真正需要的是Set，但如果规范是这样的，您可以使用哈希表来实现此目的：
下面是你是怎么做的：
- 检查您所在的节点是否为空。如果是这样的话，如果您所在的节点已经在哈希表中，则没有循环
- 检查。如果是这样，就会有一个cycle
如果不是1或2：
- 将节点添加到哈希表中，然后转到list
中的下一个节点
Stack Overflow用户
发布于 2020-06-03 05:38:06
检查这个算法。它可以很好地用于数组
var hasCycle = function(data) {
let dataLength = data.length;
let table = {};
for(let i=0 ; i < dataLength; i++ ) {
if(table[data[i]]) {
return i;
}
table[data[i]] = true;
}
return -1;
};
console.log(hasCycle([1,2,1]));// 2
console.log(hasCycle([1,2])); // -1页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62161299
复制相关文章
相似问题
腾讯云开发者
