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

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

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

Ответы

Ответ 1

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

Ответ 2

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

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

enter image description here

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

BTW, lasso - это termicus technicus из теории графов, ковбой - нет.

Ответ 3

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

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