Алгоритм обнаружения петли связанного списка

Question

Я прочитал в Интернете несколько вопросов об интервью, как найти, если в связанном списке есть петля, и решение ( Алгоритм поиска циклов Флойда ) состоит в том, чтобы иметь два указателя, один в 2 раза быстрее, чем другой, и проверьте, встретятся ли они снова.

Мой вопрос: почему я не могу просто зафиксировать один указатель, просто каждый раз перемещать другой указатель вперед на 1 шаг?

Answer 1

Поскольку, возможно, в цикле нет полного связанного списка.

Для алгоритма обнаружения связанного списка лассо необходимо два указателя:

Пока первый указатель находится там, где находится ковбой, петли не обнаружено.Но если вы пошагово продвинетесь вперед, он в конечном итоге войдет в цикл.

---

Кстати, лассо - это конечный техник из теории графов, а ковбой - нет.

Answer 2

Поскольку первый (неподвижный) указатель может не лежать в цикле, поэтому указатели никогда не встретятся. (Помните, что цикл может состоять только из части списка.)

Answer 3

Поскольку цикл может не содержать элемент, на который указывает первый указатель.

Например, если первый указатель указывает на элемент 1, а связанный список имеет цикл позже (1-> 2-> 3-> 4-> 2), ваш алгоритм его не обнаружит.