Как мы можем доказать, что перемещение быстрого и медленного указателя (с самого начала) на 1 делает точку пересечения узлом цикла? Я имею в виду, что я не могу понять, что дает ему гарантированное решение, что узел собрания является циклом узел (т. е. узел, откуда начинается цикл)
Я понятен с обнаружением петли черепахи в основном, я говорю об определении узла, где цикл начинается после того, как цикл обнаружен.Обнаружение петли связанного списка
Это очень простое доказательство. Во-первых, вы подтверждаете, что медленный указатель будет соответствовать быстрому указателю после максимум n + k шагов, где n - количество ссылок на начало цикла, а k - длина цикла. И тогда вы докажете, что они будут соответствовать снова после ровно k дальнейших шагов.
Точка, где они встречаются, будет где угодно в цикле.
Прежде чем пытаться доказать это формально, сначала вы должны взглянуть на пример, чтобы вы могли более интуитивно понятное понимание и возможность визуализации того, что происходит. Предположим, у вас есть следующий связанный список, в котором 3 (с индексом 3) указывает обратно на 1 (с индексом 1):
[0| ]->[1| ]->[2| ]->[3| ]--+
^ |
| |
| |
+------------------+
Прогулка по логической последовательности, вы можете наблюдать следующее, когда увеличивающиеся медленно по одно положение и быстро на два:
Надеюсь, это поможет!
Все еще не может найти математическое доказательство. –
Это метод обнаружения [* черепаха и зайца *] (https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare). –
Нет гарантии - насколько я знаю - вы встретитесь в узле, где начинается * цикл *. Однако метод * черепаха и заяц * гарантирует, что вы встретитесь в узле *, который является частью цикла *. –