Написание функции для обнаружения цикла в связанном списке (алгоритм Флойд) ... Логика выглядит правильно, но не может найти ошибку

Question

Я пытаюсь обнаружить цикл в связанном списке, который я создал (я тренируюсь для вопросов интервью).Я понимаю логику алгоритма Флойд-черепахи-зайца, но функция всегда возвращает ложь ...

Вот мой связанный список:

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);

Вот моя функция обнаружения цикла,возвращает false, даже если есть цикл:

 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);

Я просто не могу найти, что не так с моей функцией, и чем больше я пытаюсь выяснить это, тем более узким я становлюсь ... любое руководство будет оченьвысоко ценится!

Answer 1

Вы создаете новые узлы при каждой вставке.Например, у вас третий и восьмой узлы имеют значения 65, но они не равны (это разные объекты, поэтому условие === не будет выполнено).Что еще более важно, они имеют разные узлы .next, и ваши итераторы slwo и fast не будут возвращаться к 4-му элементу после прохождения 8-го элемента.