Логика метода определения цикла в связанном списке

Question

В лучшем способе обнаружения цикла в связанном списке мы делаем следующее:

1. Используйте алгоритм нахождения цикла Флойда и определите позицию в цикле в связанном списке.
2. Подсчитать размер цикла в связанном списке
3. Поместите один указатель в начале списка, а другой «k» (где k - размер цикла).
4. На итерации они встречаются в начале цикла.

Я хотел бы знать, почему это работает. Какая-то теоретическая логика за этим стоит?

Answer 1

Метод Floyd помогает вам определить наличие цикла, но, поскольку могут существовать некоторые узлы до начала цикла, он не может напрямую указать продолжительность цикла. Таким образом, вы должны рассчитать длину в следующем шаге. Теперь мы хотим определить начальную точку цикла. Предположим, длина цикла равна K, а число узлов от головного узла до начала цикла равно L, теперь, если вы перемещаете оба указателя вперед, они встречаются в начале цикла, потому что указатель заголовка должен идти вперед Узлы L и указатель, который K на шаг впереди, имеет две возможности. Он обязательно будет в начале цикла после узла L, потому что: Вариант 1: если он находится в цикле, он находится на узле K-L цикла и K-(K-L) = L. Выбор 2: если он вне цикла, L-K узлов остается до начала и L-K + K = L.