Почему это работает
- Если список кончается, fast первым доходит до none, и цикл останавливается: false. Сначала проверяются fast и fast.next, поэтому fast.next.next от none никогда не берётся.
- Если в списке петля, оба указателя в итоге ходят по ней по кругу. За раунд fast делает два шага, а slow один, поэтому разрыв между ними сокращается ровно на один: перепрыгнуть slow fast не может, он встаёт на него.
- «slow is fast» сравнивает узлы, а не значения: в двух разных узлах может лежать одно и то же число.
Сложность
Время O(n): fast догоняет slow раньше, чем slow обойдёт петлю один раз, поэтому slow делает меньше n шагов, а fast меньше 2n. Память O(1): два указателя и никакого множества посещённых узлов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗