Я прочитал в Интернете вопрос на собеседовании о том, как бы вы обнаружили, есть ли цикл в связанном списке, и решение (алгоритм поиска цикла Флойда) состоит в том, чтобы иметь два указателя, один в 2 раза быстрее, чем другой, и проверять, встречаются ли они снова.
Мой вопрос: почему я не могу просто зафиксировать один указатель, просто перемещая другой указатель каждый раз на 1 шаг вперед?
Поскольку первый (неподвижный) указатель может не находиться внутри цикла, указатели никогда не встретятся. (Помните, что цикл может состоять только из части списка.)
Потому что, возможно, не весь связанный список находится внутри цикла.
Для алгоритма обнаружения лассо связанного списка вам понадобятся два указателя:
Пока первый указатель находится там, где находится ковбой, цикл не обнаруживается. Но если вы пошагово двигаете его вперед, он в конечном итоге войдет в петлю.
Кстати, лассо - это технический предел теории графов, а ковбой - нет.
Потому что цикл может не содержать элемента, на который указывает первый указатель.
Например, если первый указатель указывает на элемент 1, а связанный список имеет цикл позже (1-> 2-> 3-> 4-> 2), ваш алгоритм не обнаружит его.
