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

Question

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

EDIT

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