Список с петлёй

У Вас есть указатель на первый элемент односвязного списка. Этот список может либо заканчиваться указателем на null, либо содержать петлю, т.е. ссылка из очередного элемента может указывать на один из предыдущих элементов (в том числе и на тот же самый элемент).

Примеры двух списков на рисунке:

За линейное время и константную память необходимо проверить, есть ли в списке петля. Количество элементов в списке заранее не известно.

Решение
Пустим по списку два итератора, один из которых будет идти по списку в два раза быстрее. Т.е. на каждое продвижение медленного итератора вперёд на один элемент быстрый итератор будет перескакивать на два элемента.

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

Код на Java может выглядеть вот так:

boolean hasLoop(Node first) {
    Node slowIter = first;
    Node fastIter = first;
    while (true) {
        for (int i=0; i<2; i++) {
            if (fastIter == null) {
                return false;
            }
            fastIter = fastIter.next;
            if (fastIter == slowIter) {
                return true;
            }
        }
        slowIter = slowIter.next;
    }
}