Учитывая связанный список и количество для поворота, верните связанный список, повернутый против часовой стрелки.
Например, учитывая связанный список…
1 → 2 → 3 → 4 → 5 → 6
… и число поворотов 2, связанный список должен выглядеть так:
3 → 4 → 5 → 6 → 1 → 2
Вы можете предположить, что количество поворотов меньше, чем длина связанного списка.
Лучший способ сделать это требует только одного прохода связанного списка для временной сложности O (n).
В основном вам нужно выполнить итерацию один раз по связанному списку, сохраняя указатели на:
- Текущий конец неперевернутого связанного списка
- Узел, который станет хвостом повернутого связанного списка
Когда у вас есть эти местоположения в связанном списке, сохраненном в переменных, ротация становится тривиальной. Вот как мы это сделаем.