Доказательство обнаружения начала цикла в связанном списке [дубликат]
На этот вопрос уже есть ответ здесь:
Из нескольких сообщений внутри stackoverflow и за его пределами я узнал как определить циклы в связанном списке, длину цикла. Я также нашел метод, как определить начало цикла.
Вот шаги еще раз для справки.
Обнаружение цикла:
Есть два указателя, классически называемые заяц и черепаха. Переместите зайца на 2 шага, а черепаху - на 1. Если они встречаются в какой-то момент, то наверняка существует цикл, и точка встречи, очевидно, находится внутри цикла.
Определение длины цикла:
Удерживайте один указатель на месте в точке встречи, а другой увеличивайте, пока они снова не станут такими же . Увеличивайте счетчик по мере продвижения, и значение счетчика на встрече будет длиной цикла.
Найдите начало цикла
Возьмите один указатель в начало списка и оставьте другой в точке встречи. Теперь увеличивайте и на единицу, и точка встречи - это начало цикла. Я проверил этот метод, используя несколько примеров на бумаге, но я не понимаю, почему он должен работать.
Может ли кто-нибудь предоставить математическое доказательство того, почему этот метод работает?