Реверс связанного списка
12 декабря 2022 г.По заданному заголовку односвязного списка перевернуть список и вернуть перевернутый список.
Пример 1:
Ввод: head = [1,2,3,4,5]
Вывод: [5,4,3,2,1]
Пример 2:
Ввод: head = [1,2]
Вывод: [2,1]
Пример 3:
Ввод: head = []
Вывод: []
Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000]. -5000 <= Node.val <= 5000
Последующие действия. Связанный список можно реверсировать итеративно или рекурсивно. Не могли бы вы реализовать оба варианта?
Решение
Подход 1: итеративный
def reverse_list(head: ListNode) -> ListNode:
prev = None
current = head
while current:
next = current.next
current.next = prev
prev = current
current = next
return prev
https://youtu.be/LcKcMDP6WwU?embedable=true
Сложность пространства: O(1) Временная сложность: O(n)
Подход 2: рекурсивный
def reverse_list(head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = reverse_list(head.next)
head.next.next = head
head.next = None
return new_head
Пространственная сложность: O(n) Временная сложность: O(n)
Оригинал