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

Question

Итак, есть несколько вопросов о том, как определить цикл в связанном списке. Here - один пример. Мой вопрос в том, почему все эти алгоритмы используют два указателя? Не могли бы вы просто пройти через один указатель и пометить узлы как посещенные, и когда вы перейдете к узлу, который вы уже посетили или достигли конца связанного списка (next = null), то вы знаете, что нет цикла ?

Answer 1

Это потому, что в

маркировать узлы как посещенные

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

[EDITED add:] ... И, возможно, также потому, что решения с двумя указателями являются умными, и люди любят умные решения вещей.