Вопрос на собеседовании #2

Задача в довольно большой, но не IT компании. Туда я вообще не прошел, так как шел на разработку в незнакомую область, но опыт прикольный =)

Задача:
Условие взял отсюда.
Есть односвязный список

struct List { int value; struct List *next; } _list;

требуется написать функцию

bool isCycled(struct List *head);

определяющую, есть ли в списке цикл, при этом потребление памяти не должно зависеть от размера списка.





Решение:
Ну я сразу ответа на задачу не нашел. Хотя и времени у меня с минуту было...проговорил пару вариантов, и тут же и отверг...map/set создать не можем, по памяти не проходим. По времени поиска ответа не ограничен, значит можно писать что-то не эффективное.

В сети предлагают вариант с медленным и быстрым указателем, и мы либо дойдем быстрым указателем до крайнего элемента, либо медленный с быстрым когда-то сравняются.

Предлагаются еще решения, но я их толком не разбирал.

Немного подумав придумал следующее решение:

Указатели наверняка указывают на пространство в куче, она не бесконечная, да у нас и в принципе нет бесконечных носителей. Учитывая эти факты: будем отмечать минимальный и максимальный указатель из встречающихся и считать количество указателей после факта смены максимального или минимального указателя. Теперь если текущий указатель с NULL в *next, то список не цикличный. Если текущий указатель равен минимальному(pMin) или максимальному(pMax) указателю, то список цикличный. Если (pMax - pMin) / count < sizeof(List), то список цикличный, ну или что-то вроде такого =) Идею проверял только в уме, может есть в ней баг)

А какие у Вас есть решения данной задачи?

Другие части цикла: #1 #3 #4 #5