| 11:59p |
Алгоритм cycle detection (списка / односвязной компоненты унара) - это жемчужина.
Придумал его с одной подсказки (ну, или почти с одной): второе название у техники - 2-pointers. Техника более общая, это один из вариантов. Реально было бы догадаться, и просто отталкиваясь от требования О(1) по памяти, но увы, теперь его идею забыть невозможно.
После размышлений копнул глубже и нашёл длины префикса и цикла. |