Почему это работает
- За раунд fast делает два шага, а slow один, поэтому fast всегда вдвое дальше от головы, чем slow. Когда у fast кончается список, slow прошёл ровно половину.
- При чётной длине fast останавливается на none после n / 2 раундов: slow тогда на узле n / 2 + 1, втором из средних. При нечётной fast останавливается на последнем узле, а slow — на единственном среднем.
- Длину списка никто не считает: один проход, и когда остановиться, решает только условие цикла.
Сложность
Время O(n): fast проходит список один раз, по два узла за раунд, а slow — половину. Память O(1): два указателя.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗