Задача с собеседования в Zopsmart

Дана голова односвязного списка. Разверните список и верните его.

Follow-up: связный список можно развернуть как итеративно, так и рекурсивно. Могли бы вы реализовать оба способа?

Пример 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Пример 2:
Input: head = [1,2]
Output: [2,1]

Пример 3:
Input: head = []
Output: []

Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
-5000 <= Node.val <= 5000

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
В односвязном списке каждый узел хранит данные и ссылку на следующий элемент (или None, если узел последний).
Чтобы развернуть список, нужно изменить указатели всех узлов на противоположные.

Итеративно:
reversed_head - голова развёрнутого списка (сначала None, так как развёрнутый список пуст).
head - узел, с которым работаем (текущий обрабатываемый узел исходного списка).
head.next - указатель текущего узла, его направление будем менять.

Идём до конца исходного списка, на каждой итерации обрабатывая head:
- сохраняем узел, следующий за head, в переменную next_node, чтобы не потерять остаток списка после разрыва связи между узлами;
- операция разворота: указатель текущего узла теперь указывает на голову развёрнутой части;
- обновляем голову развёрнутой части: теперь она начинается с текущего узла;
- переходим к сохраненному остатку исходного списка.
В конце возвращаем голову развёрнутого списка.

Сложность:
O(n) - по времени (проходим по списку один раз)
O(1) - по памяти (храним три указателя, разворачиваем ссылки на месте)

Код:
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        reversed_head = None

        while head:
            next_node = head.next
            head.next = reversed_head
            reversed_head = head
            head = next_node

        return reversed_head


Рекурсивно:
Сначала уходим в конец списка, достигая базового случая, а потом идём в обратном порядке, переворачивая указатели.

Базовый случай:
если исходный список пуст или следующий узел отсутствует. Последний узел становится головой развёрнутого списка, рекурсия останавливается.

Рекурсивный случай:
вызываем функцию для остатка исходного списка и получаем reversed_head - последний узел исходного списка, ставший головой (ссылка на него не меняется во время работы алгоритма).
После достижения базового случая поднимаемся по стеку вызовов:
- меняем указатель у узла, следующего за head, на head. Теперь они ссылаются друг на друга;
- разрываем старую связь между узлами: head указывает на None и становится последним узлом в развёрнутой части;
- возвращаем голову развёрнутого списка.

Сложность:
O(n) - по времени (кол-во вызовов равно длине списка)
O(n) - по памяти (рекурсия линейная)

Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head

reversed_head = self.reverseList(head.next)
head.next.next = head
head.next = None

return reversed_head

@algoses