Препод по программированию задал задачку. Что-то никак не соображу, как решается.
Задача по Динамическим структурам данных, по паскалю в частности. Хотя жёстко к языку не привязана. Так что интересует алгоритм решения а не реализация . Вообще задача вроде как стандартная и видел много вопросов по ней. Но вот решения, которое подходит мне не нашёл.
Есть однонаправленный список, который может быть зациклен
Задание такое – определить зацикленный ли список?
Данные и условия:
Список может быть зациклен не только на предыдущий элемент. Т.е решение запустить 2 прохода по списку с разным шагом в 2 не подходит.
Перезаписывать, добавлять что-либо в самом списке нельзя. Т.е добавить флаг-" здесь мы были" нельзя.
Создавать переменные, которые зависят от количества элементов в цикле нельзя. Т.е создать ещё список с пройденными адресами нельзя.
Количество элементов списка (N) неизвестно. И максимальное количество проходов по списку, за которое точно можно будет сказать, что список не зациклен (или зациклен), не должно превышать N. Т.е тупой поиск в пройденных элементах использовать нельзя.
Вродь всё)
Я уже и не знаю что делать. Мож что-нить связанное с указателями и памятью тут? Помогите пожалуйста)
Как раз то, что нужно. 