Почему это работает
- fast стартует на n узлов впереди, дальше оба идут по одному шагу, и разрыв остаётся n. Когда fast на последнем узле, slow — (n + 1)-й с конца, прямо перед удаляемым.
- Чтобы удалить узел, перецепляют узел перед ним. Фиктивный узел даёт такой узел даже голове, поэтому n, равное длине, не требует отдельного случая: slow просто не уходит с dummy.
- По той же причине ответ — dummy.next, а не head: когда удалена голова, head всё ещё указывает на неё.
Сложность
Время O(L), где L — длина списка: fast проходит его один раз, а slow идёт следом. Память O(1): два указателя и один фиктивный узел.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗