Контест Middle Связные списки спрашивают часто обновлено
Есть ли цикл в списке и какой он длины
Условие
Односвязный список из n узлов задан массивом next: из узла i указатель ведёт в узел nextᵢ, а 0 означает конец списка. Голова списка в узле 1. Пройдите от головы по указателям. Если путь зацикливается, выведите длину цикла (число узлов в нём), иначе 0.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел next₁ … nextₙ (0 ≤ nextᵢ ≤ n). На узел могут указывать несколько других узлов.
Вывод: длина цикла или 0.
Попробуйте решить с O(1) дополнительной памяти, как будто список настоящий, а массив вам не дан.
Пример 1
Ввод:
5
2 3 4 5 3
Вывод:
3
Пример 2
Ввод:
3
2 3 0
Вывод:
0
Как подойти
Подсказки: 2
- Два указателя с разной скоростью встретятся, если есть цикл.
- После встречи пройдите цикл один раз и посчитайте шаги.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.