Список brainteasers Домой

Территория Web 1.0 / Brainteasers

Цикл в списке

Пусть список - это структура, состоящая из конечного числа элементов; каждый элемент состоит из двух частей: поля данных и поля, указывающего на следующий элемент списка или на специальный элемент, обозначающий конец списка (null pointer). Пример из "реального мира": книга, представленная в виде набора web-страниц с текстом, в конце каждой страницы ссылка на следующую.

Говорят, что список имеет цикл, если существует элемент, указывающий на некоторый другой элемент, идущий в списке раньше. Например, пусть есть список из 10 элементов (первый указывает на второй, второй на третий и т.п.). Если десятый элемент указывает на null, в списке нет цикла, если же он указывает на какой-то из элементов [1-9], в списке цикл есть.

Пусть имеется список, записанный на некотором большом носителе (объем которого заранее не известен), содержимое которого мы не можем модифицировать (DVD). В нашем распоряжении имеется компьютер с ограниченным объемом памяти. Требуется придумать алгоритм, позволяющий определить, есть ли в списке цикл.

Подсказка [1]
Подсказка [2]
Ответ [A]
Ответ [B]


16.03.2010