Как определить, содержит ли связанный список цикл?

Question

Возможные Дубликаты:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

Во время подготовки к собеседованию, я столкнулся следующий вопрос:

Как вы можете определить, является ли связанный список (любого типа) содержит цикл, используя additio (1)? Вы не можете предположить, что цикл начинается с первого узла (и, конечно, цикл не должен содержать всех узлов).

я не мог найти ответ, хотя у меня есть ощущение, что это довольно просто ...

Answer 1

Easy. Поддержание двух указателей в списке. На каждом шаге продвигайте один указатель по одной ссылке и продвигайте вторую по двум ссылкам. Проверьте, указывают ли они на один и тот же элемент. Если это так, у вас есть цикл. Если нет, повторите, пока не найдете цикл или вы не дойдете до конца списка.

Answer 2

Возможно, такая же методика, как проверка, является ли граф деревом (деревья не имеют циклов), см. this this question. Он рекомендует либо топологическую сортировку, либо первый поиск глубины.

Answer 3

У меня была эта точная проблема с реальным кодом на прошлой неделе.

Все, что я сделал, содержал указатель (ссылка) для первого элемента. Затем, когда я перебирал список, если я когда-либо получил этот указатель, я знаю, что есть цикл.