Алгоритм поиска цикла Флойда

Алгоритм поиска циклов Флойда или алгоритм Зайца-Черепахи — это алгоритм указателей, использующий только два указателя, перемещающихся по последовательности с разной скоростью. Этот алгоритм используется для поиска цикла в связанном списке. Он использует два указателя, один из которых движется в два раза быстрее, чем другой. Более быстрый указатель называется более быстрым указателем, а другой называется медленным указателем.

Как работает алгоритм поиска цикла Флойда?

При обходе связанного списка произойдет одна из следующих вещей:

• Указатель Fast может достигать конца (NULL), это показывает, что в связанном списке нет цикла.
• Быстрый указатель снова ловит медленный указатель в какой-то момент, поэтому в связанном списке существует петля.

Пример:

Псевдокод:

• Инициализируйте двухуказатели и начните обход связанного списка.
• Переместите медленный указатель на одну позицию.
• Переместите быстрый указатель на две позиции.
• Если оба указателя встречаются в какой-то точке, то существует петля, и если быстрый указатель достигает конечной позиции, то петли не существует.

Ниже приведена программа на C++ для реализации описанного выше подхода:

Временная сложность: O(n), так как цикл проходится один раз.
Вспомогательное пространство: O(1), используются только два указателя, поэтому постоянная сложность пространства.

Почему алгоритм Флойда работает?

Рассмотрим пример:

• Позволять,

X = Distance between the head(starting) to the loop starting point.

Y = Distance between the loop starting point and the first meeting point of both the pointers.

C = The distance of the loop

• Итак, прежде чем указатель встретится

The slow pointer has traveled X + Y + s * C distance, where s is any positive constant number.

The fast pointer has traveled X + Y + f * C distance, where f is any positive constant number.

• Поскольку быстрый указатель движется в два раза быстрее, чем медленный указатель, мы можем сказать, что быстрый указатель преодолел в два раза большее расстояние, чем медленный указатель. Следовательно-

 X + Y + f * C = 2 * (X + Y + s * C)

X + Y = f * C – 2 * s * C

We can say that,

f * C – 2 * s * C = (some integer) * C

                         = K * C

Thus,

X + Y = K * C       – ( 1 )

X = K * C – Y        – ( 2 )

Where K is some positive constant.    

• Теперь, если сбросить медленный указатель на голову (начальное положение) и перемещать как быстрый, так и медленный указатель на одну единицу за раз, можно заметить из 1-го и 2-го уравнения, что оба они встретятся после прохождения X расстояния в начале петля, потому что после сброса медленного указателя и перемещения его на расстояние X, в то же время от точки встречи цикла быстрый указатель также пройдет расстояние K * C - Y (поскольку он уже прошел расстояние Y).
• Из уравнения (2) можно сказать, что X = K * C – Y, следовательно, оба указателя пройдут расстояние X, т.е. одно и то же расстояние после розового узла в какой-то точке, чтобы встретиться в начальной точке цикла.
• Здесь в какой-то момент это означает, что быстрый указатель может пройти расстояние K * C, из которого он уже прошел расстояние Y.

Ниже приведена программа C++ для реализации описанного выше подхода.

Временная сложность: O(n), так как мы прошли цикл один раз, а затем прошли расстояние X.
Вспомогательное пространство: O(1), так как используются только указатели, поэтому постоянная сложность пространства.