Почему это работает
- Каждые length поворотов возвращают список в исходный вид, поэтому важны только k mod length поворотов. k может быть намного больше списка, поэтому сначала считаем длину.
- Поворот на k переносит последние k узлов в начало. fast уходит на k узлов вперёд, и когда он на хвосте, slow стоит прямо перед этими k узлами: после него и режем.
- Поворот делают три ссылки: хвост на старую голову, head на slow.next, slow.next на none. При k mod length = 0 slow останавливается на хвосте, и те же три ссылки возвращают список без изменений.
Сложность
Время O(n): один проход, чтобы посчитать, и ещё один проход fast по списку; после mod само k не важно. Память O(1): несколько указателей, узлы перецепляются, а не копируются.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗