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