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