I am trying to detect a cycle in a linked list I created (I'm practicing for interviews questions). I understand the logic involved in Floyd's tortoise-hare algorithm but the function is always returning false...
Here's my linked list:
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);
Here is my cycle-detection function, it returns false even if there is a cycle:
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);
I just cannot find what's wrong with my function and the more I try to figure it out the more narrow minded I become... any guidance would be very much appreciated!
You're creating new nodes each insertion. E.g. you're 3rd and 8th nodes both have values 65, but are not equal (they're different objects, so the ===
condition will fail). More importantly, they have different .next
nodes and your slwo
and fast
iterators will not loop back to the 4th element after traversing the 8th element.