Очень распространенная задача на интервью в Майкрософт:

Есть связанный список. Нужно выяснить, не "сломался" ли он. Т.е. последний элемент стал указывать не на NULL, а на какой-то элемент посредине.

Простейшее решение - понятно. Проходим по списку, для каждого текушего элемента проходим еще раз и смотрим, был ли уже этот элемент в списке, или нет. Если был - значит зацикленый список, если дошли до NULL - значит нет. Сложность такого решения - квадрат длины списка.

Оптимизация - идти по списку и заносить элементы в хеш-таблицу. Тогда проверка, был ли уже элемент займет константное время и сложность такого решения линейна. Однако, требуется O(n) памяти для таблицы.

Существует линейное решение, не требуещее памяти. Напишу его в следующий раз, а если есть идеи - оставьте в комментариях.