编写一个函数来检测链表中的循环(Floyd 算法)...逻辑看起来正确但找不到错误
Writing a function to detect a cycle in a linked list (Floyd's alg)... Logic looks correct but can't find the bug
我正在尝试检测我创建的链表中的循环(我正在练习面试问题)。我了解 Floyd 的龟兔赛跑算法中涉及的逻辑,但该函数始终返回 false...
这是我的链表:
class LinkedList {
constructor() {
this.length = 0;
this.head = null;
}
insert(index, value) {
if (index < 0 || index > this.length) {
throw new Error("Index error");
}
const newNode = {
value
};
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
} else {
const node = this._find(index - 1);
newNode.next = node.next;
node.next = newNode;
}
this.length++;
}
...
}
//Inserting values
const linkedList = new LinkedList();
linkedList.insert(0, 12);
linkedList.insert(1, 24);
linkedList.insert(2, 65);
linkedList.insert(3, 23);
linkedList.insert(4, 9);
linkedList.insert(5, 7);
linkedList.insert(6, 13);
linkedList.insert(7, 65);
linkedList.insert(8, 20);
这是我的循环检测函数,它 returns 即使有循环也是错误的:
function containsCycle(firstNode) {
// Start both at beginning
let slow = firstNode;
let fast = firstNode;
// Until end of the list
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
// fast is about to "lap" slow
if (fast === slow) {
return true;
}
}
// fast hit the end of the list
return false;
}
//Calling function
containsCycle(linkedList.head);
我就是找不到我的函数有什么问题,我越想弄清楚它就越心胸狭隘……非常感谢任何指导!
每次插入都会创建新节点。例如。你是第 3 个和第 8 个节点,它们的值都是 65,但不相等(它们是不同的对象,因此 ===
条件将失败)。更重要的是,它们有不同的 .next
节点,你的 slwo
和 fast
迭代器在遍历第 8 个元素后不会循环回到第 4 个元素。
我正在尝试检测我创建的链表中的循环(我正在练习面试问题)。我了解 Floyd 的龟兔赛跑算法中涉及的逻辑,但该函数始终返回 false...
这是我的链表:
class LinkedList {
constructor() {
this.length = 0;
this.head = null;
}
insert(index, value) {
if (index < 0 || index > this.length) {
throw new Error("Index error");
}
const newNode = {
value
};
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
} else {
const node = this._find(index - 1);
newNode.next = node.next;
node.next = newNode;
}
this.length++;
}
...
}
//Inserting values
const linkedList = new LinkedList();
linkedList.insert(0, 12);
linkedList.insert(1, 24);
linkedList.insert(2, 65);
linkedList.insert(3, 23);
linkedList.insert(4, 9);
linkedList.insert(5, 7);
linkedList.insert(6, 13);
linkedList.insert(7, 65);
linkedList.insert(8, 20);
这是我的循环检测函数,它 returns 即使有循环也是错误的:
function containsCycle(firstNode) {
// Start both at beginning
let slow = firstNode;
let fast = firstNode;
// Until end of the list
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
// fast is about to "lap" slow
if (fast === slow) {
return true;
}
}
// fast hit the end of the list
return false;
}
//Calling function
containsCycle(linkedList.head);
我就是找不到我的函数有什么问题,我越想弄清楚它就越心胸狭隘……非常感谢任何指导!
每次插入都会创建新节点。例如。你是第 3 个和第 8 个节点,它们的值都是 65,但不相等(它们是不同的对象,因此 ===
条件将失败)。更重要的是,它们有不同的 .next
节点,你的 slwo
和 fast
迭代器在遍历第 8 个元素后不会循环回到第 4 个元素。