Проблема исходного псевдокода в том, что он не проверяет достижение конца списка (то есть `node == null`) и сразу делает `node = node.next`. В результате при списке без цикла алгоритм либо вызовет ошибку при обращении к `null.next`, либо (в редких реализациях/языках с особыми семантиками) может застрять в бесконечном повторном посещении `null`. Кроме того, сам код всегда возвращает `true` после выхода из цикла, тогда как при отсутствии цикла должен возвращать `false`.
Правильная версия с множеством посещённых узлов:
- Идея: при обходе, если встретили уже посещённый узел — цикл есть; если дошли до конца (`null`) — цикла нет.
Псевдокод:
function findCycle(node):
visited = set()
while node != null:
if node in visited:
return true
visited.add(node)
node = node.next
return false
Время: $\mathrm{O}(n)$, память: $\mathrm{O}(n)$.
Эффективный алгоритм без доп. памяти — алгоритм Флойда (“черепаха и заяц”):
- Два указателя: slow двигается по одному шагу, fast — по двум. Если есть цикл, они встретятся; если нет — fast дойдёт до конца.
Псевдокод:
function findCycle(node):
if node == null: return false
slow = node
fast = node
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast:
return true
return false
Время: $\mathrm{O}(n)$, память: $\mathrm{O}(1)$.