В продолжение задач с собеседований

— Итак, вы готовы отвечать? — Я не понял вопрос, поставьте его по-другому. — ¿ — А мне нравится ваш подход!

На собеседовании.

Предыдущие задачи были здесь, здесь и здесь.

Одна из самых известных задач на собеседованиях формулируется следующим образом:

У вас есть однонаправленный связный список, то есть адрес первого узла этого списка. В каждом узле есть поле данных, которое трогать нельзя, и поле next с адресом следующего элемента списка. Есть шанс, что список зациклен, то есть существует вероятность, что у последнего узла поле next содержит не NIL (символ окончания списка), а адрес одного из уже пройденных узлов. Какого именно — неизвестно. Предложите простой способ проверить зацикленность списка, используя минимум дополнительных ресурсов.

( Под катом — два решения. )