如何使用哈希表在单向链表中查找循环?

Question

我知道这是一个常见的问题，但我发现没有答案与我的算法不同，但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 循环中，第一次迭代将 table[1] 设置为 true。在第二次迭代中，表 [2] 设置为 true。然后我们退出 while 循环，因为节点现在指向 null，所以我的代码应该返回 false。但是，leetcode 说我的算法返回 true。我哪里犯了错误？

我知道龟兔算法，但我正在尝试理解哈希表方法来找到一个循环。

Answer 1

本质上，您需要做的是遍历列表，看看哪个先到？列表的末尾或以前访问过的节点。您可以使用 Hashtable 来记录您访问过的节点，虽然您真正需要的是Set，但如果规范是这样，您可以使用哈希表来实现此目的：

以下是您的操作方法：

1. 检查您所在的节点是否为空。如果是这样，则没有周期
2. 检查您所在的节点是否已在哈希表中。如果是这样，则有一个循环

如果不是 1 或 2：

3. 将节点添加到哈希表
4. 转到列表中的下一个节点

Answer 2

检查此算法。它适用于数组

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