Занимательные алгоритмы. Поиск цикла в односвязном списке

И снова про тараканов, которые иногда возникают в голове. Как-то раз, засыпая, я задумался на курьезными задачками из своей сферы деятельности (Lotus Notes), которые можно было бы задать на собеседовании, плавно перешел к воспоминаниям о своих первых собеседования, когда опыта работы еще не было. Опыт самих собеседований у меня не велик а места, где задавались действительно интересные задачи (а не задачки типа: написать сортировку массива любым известным способом) вообще равны одному - это ABBYY. Как минимум одна задачка в списке на знание и понимание классических алгоритмов, описанных в книге Дональда Кнута - Искусство программирования.

Возвращаясь к моим мыслям: вспомнилась мне одна задачка из интересных и, в общем, не мог уснуть - пытался решить ее или вспомнить решение. К сожалению, сходу я решение не придумал и пришлось даже подглядывать в гугле. Правда, решение, которое я там обнаружил не было похоже, на известное мне. Итак, по порядку.

Задача: Дан однонаправленный список (указатель на его первый элемент). Определить, имеется ли в списке цикл за кол-во операций O(n), где n - кол-во элементов в списке и используемой дополнительной памяти О(1).

Ограничения, накладываемые условиями:

1. Кол-во элементов - n - конечно, но не известно;

2. Сравнение текущего "индекса" с n не возможно, исходя из п.1;

3. Сравнение каждого с каждым и использование других структур данных не возможно, исходя из условий по сложности и используемой памяти;

4. Нельзя изменять содержимого элемента списка.

Решение 1: 

Стандартный алгоритм, решающий данную задачу с указанными ограничениями основывается на двух указателях (p1 и p2), пускаемых по списку с шагом 1 и 2 элемента. Если в какой-то момент времени указатель p2 догонит p1 => цикл существует. Описание алгоритма и его доказательство рассматривается много где. Наверно наиболее подробно вопросы зацикливания рассмотрены тут.

Не претендую на уникальность, но, полагаю, что предложенный ниже алгоритм - имеет право на существование, т.к. удовлетворяет всем условиям задачи и накладываемым ограничениям.

Решение 2:

1. Будем идти по списку (сохранив указатель на первый элемент) и переворачивать указатели, образовывая обратный список

2. Если один прекрасный момент указатель на след. элемент будет не определен => цикла нет. Далее см. п. 4.

3. Если мы вернулись к изначальному указателю (на рисунках видно каким образом) => цикл есть. Далее см. п. 4.

4. Для возврата к исходному состоянию списка - пройдемся в обратном направлении, разворачивая указатели.

Итого будет выполнено не более 2n + 2n операций (если цикл на последних элементах), а исходя из определения, O(2n + 2n) = O(4n) = O(n). Количество необходимой памяти в каждый момент: указатель на первый элемент списка + 3 указателя на 3 последовательных элемента списка (для их корректного "разворота") => O(1 + 3) = O(4) = O(1). Вроде нигде ничего не напутал.

Контакты: