Обнаружение петли в связанном списке

Question

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

Answer 1

Алгоритм Брента явно лучший здесь: для списков без петель он просто посещает список один раз, в то время как черепаха и заяц Флойда требуют пересмотреть половину узлов.Для списков с циклами он никогда не «вращается» дольше в цикле, чем Floyd;и в лучшем случае нужен только один цикл, когда Флойд нуждается во многих.Подумайте о длинной последовательности без петель, за которой следует цикл длины 1. В этом случае наилучшим вариантом для Брента будет обнаружение цикла после одного посещения цикла - поэтому посещение каждого узла происходит ровно один раз;тогда как Флойд должен посещать каждый узел в среднем три раза.

Основная идея состоит в том, чтобы посетить связанный список и сравнить указатель текущего узла с одним уже посещенным узлом.То есть сравнение одного указателя на посещаемый узел.Указатель обновляется время от времени, следуя простой логике.

Answer 2

Вы можете использовать hastable для хранения посещенных узлов по мере продвижения по связанному списку, если не возражаете против дополнительной памяти O (N).

На каждом узле вы проверяете, существует ли этот узел в хеш-таблице. Если это так, вы нашли петлю. В противном случае вы добавляете его в хеш-таблицу и переходите к следующему узлу.

Answer 3

Если ваши узлы состоят из значения и указателя на следующий узел, вы можете использовать список, создав указатель на первый узел. На каждом узле можно проверить, имеет ли указатель то же значение, что и указатель на первый узел.