Подсчитайте количество узлов в связанном списке, который может быть циклическим

Question

Вот в чем проблема, она взята из превосходных алгоритмов Седжвика на Java (q 3.54)

Дана ссылка на узел в односвязном списке, который не содержит нулевых ссылок (т. е.каждый узел ссылается либо на себя, либо на другой узел в списке) определяет количество различных узлов без изменения какого-либо из узлов и использует не более постоянного объема памяти.

Как вы это делаете?просмотрите список один раз, используя алгоритм зайца и черепахи, чтобы определить, является ли он каким-либо образом круглым, а затем просмотрите еще раз, чтобы определить, где список становится круглым, затем просмотрите еще раз, подсчитывая количество узлов в этой позиции?для меня это звучит немного грубо, я думаю, есть гораздо более элегантное решение.

Answer 1

алгоритм черепах и зайцев может дать вам длина цикла и количество узлов до начала цикла (соответственно λ и μ).

Answer 2

Наиболее элегантным решением является алгоритм поиска циклов Флойда: http: //en.wikipedia. орг / вики / Cycle_detection # Tortoise_and_hare

Он запускается за время O (N), и требуется только постоянный объем памяти.

Answer 3

Проверьте это: Головоломка: Цикл в связанном списке

  

Указатель маркировки: на практике, связанный   списки реализованы с использованием структур C   по крайней мере с указателем; такая структура   в C должен быть 4-байтовым. Итак   наименее значимые два бита являются нулями.   Просматривая список, вы можете   «Отметить» указатель как пройденный   листать наименее значимый бит.   Второй обход для очистки этих   биты.

Answer 4

просто вспомните, где вы были, и если вы пришли на тот же узел, то все кончено.

Попробуйте сохранить записи в двоичном дереве, и у вас получится O (N * логарифмическая (N)) сложность во времени и O (N) пространстве

Редактировать

Вы можете использовать логарифмическую (N) пространственную сложность, если вы сохраняете не каждую ссылку, а в экспоненциальном порядке.Это означает, что вы сохраняете 1-й, 2-й, 4-й, 8-й, 16-й, а затем, если вы получите удар, вы должны продолжить с этой точки.Временная сложность для этого равна N * Log (n) ^ 2