Task 32. Найти начало цикла в односвязном списке

Задача: Дан односвязный список с циклом, найти начало этого цикла.

Идея: Воспользуемся идеей поиска цикла в односвязном списке с двумя указателями с разными шагом. То что два указателя встретятся в цикле очевидно (читать матчасть).

Итак у нас есть два указателя: slow, faster (быстрее в 2 раза чем slow), тогда получаем:

1. Расстояние пройденное slow до встречи с fast: x + y
2. Расстояние пройденное fast до встречи c slow: (x + y + z) + y = x + 2y + z

Так как указатель fast перемещается в 2 раза быстрее чем slow, получаем:

2 (x + y) = x + 2y + z

2x + 2y = x + 2y + z

x = z

Таким образом, чтобы найти начало списка:

1. Помещаем один из указателей на начало списка, второ оставляем в точке встречи

2. Запускаем оба указателя с шагом 1.

3. Теперь два указателя встретятся в точке начала цикла

Реализация:

https://gist.github.com/unilecs/4a7519a22bdac514d838a9ee94e5e0f2

Тест:

https://dotnetfiddle.net/45zuwK