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

Задача с собеседования в 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