Алгоритм поиска цикла Флойда известен тем, что определяет, содержит ли связанный список цикл. Этот алгоритм также называют алгоритмом Зайца-Черепахи из-за использования медленного и быстрого указателя.
Как это работает
Алгоритм начинается с установки двух указателей на начало связанного списка.
В каждом цикле быстрый указатель будет двигаться в два раза быстрее, чем медленный. Таким образом, медленный указатель переместится на одно место, а быстрый указатель переместится на два места.
Этот алгоритм будет определять наличие цикла либо по тому, что быстрый указатель достигает нулевого значения, что означает отсутствие цикла, либо по тому, что медленный указатель и быстрый указатель становятся одинаковыми, что означает, что цикл присутствует.
В примере в следующем цикле быстрый указатель вернется к началу цикла (4), а затем переместится во второй раз к 2. Медленный указатель также переместится на одно место к 2, и алгоритм обнаружит, что быстрый и медленный указатель имеют одно и то же значение, означающее наличие цикла.
Если трудно понять, почему указатели в конечном итоге будут иметь одинаковое значение, вы можете подумать о двух людях, идущих по дорожке. Если они оба начинают в одной и той же точке, и один человек проходит один шаг за раз, а другой человек делает два шага за раз, когда первый человек заканчивает свой первый круг, второй человек будет заканчивать свой второй круг.
Я буду демонстрировать этот алгоритм, используя задачу LeetCode.
В задаче LeetCode «Цикл связанного списка II» вам нужно обнаружить цикл и вернуть начальную точку цикла.
Для начала создайте два указателя.
Чтобы определить, присутствует ли цикл, вы создадите цикл while, который будет выполняться до тех пор, пока быстрый указатель не станет нулевым или точка рядом с быстрым указателем не станет нулевой. Внутри цикла вы будете перемещать медленный указатель один раз и быстрый указатель дважды. Чтобы завершить этот цикл, вы добавите оператор if, который прервет цикл, если медленные и быстрые указатели равны.
Как только этот цикл while завершится, вы проверите быстрый указатель, чтобы определить, был ли цикл.
После этого вы установите любой указатель в положение головы. Создайте новый цикл while, который выполняется до тех пор, пока быстрый и медленный указатели не сравняются. Затем вы будете перемещать каждый указатель на единицу, пока они не станут одинаковыми. Затем вы вернете указатель, который вы установили, в положение головы.
В приведенном выше примере мы установили быстрый указатель на положение головы.
Если оба указателя перемещаются на единицу, следующая позиция будет иметь быстрый указатель на 6 и медленный указатель на 3.
Если мы сделаем еще одно движение, медленный указатель будет перемещен в начало цикла, а быстрый указатель также переместится в начало цикла.
Полный код на C#
