Разворот односвязного списка
Дан односвязный список head. Разверните список и верните новый его начало.
Ограничения:
- Длина списка:
0 <= длина <= 1000. - Значение узла:
-1000 <= Node.val <= 1000.
Пример 1:
Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1]
Пример 2:
Input: head = [] Output: []
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью
O(1) для итеративного подхода или O(n) для рекурсивного подхода, где n —
длина списка.
Подсказка 1
Решение грубой силы заключалось бы в создании нового списка и копировании элементов в обратном порядке. Это было
бы решение с временной сложностью O(n) и пространственной сложностью O(n). Можете ли вы
придумать более эффективный способ?
Подсказка 2
Можно ли развернуть список, изменяя ссылки между узлами, без использования дополнительной памяти?
Подсказка 3
Используйте три указателя: `prev`, `curr` и `next`. Перемещайте их по списку, изменяя направление ссылок.