Лучший алгоритм, чтобы проверить, есть ли у связанного списка цикл - PullRequest
32 голосов
/ 29 августа 2008

Какой лучший (остановочный) алгоритм для определения наличия в связанном списке цикла?

[Редактировать] Анализ асимптотической сложности как по времени, так и по пространству был бы приятен, поэтому ответы можно было бы сравнить лучше.

[Редактировать] Первоначальный вопрос не касался узлов с outdegree> 1, но есть некоторые разговоры об этом. Этот вопрос больше похож на «Лучший алгоритм обнаружения циклов в ориентированном графе».

Ответы [ 13 ]

0 голосов
/ 29 августа 2008

Алгоритм Конрада Рудольфа не будет работать, если цикл не указывает на начало. Следующий список сделает его бесконечным циклом: 1-> 2-> 3-> 2.

Алгоритм DrPizza - определенно правильный путь.

0 голосов
/ 29 августа 2008

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

0 голосов
/ 29 августа 2008

Как насчет использования хеш-таблицы для хранения уже увиденных узлов (вы смотрите их по порядку с начала списка)? На практике вы можете достичь чего-то близкого к O (N).

В противном случае использование отсортированной кучи вместо хеш-таблицы приведет к O (N log (N)).

...