Решение задачи с собеседования Reverse Linked List [+ ВИДЕО]
На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: https://leetcode.com/problems/reverse-linked-list
Дан указатель head
на начало односвязного списка, необходимо развернуть список и вернуть развернутый список.
1. Решение с использованием массива
Одним из способов решения этой задачи является использование массива для хранения всех узлов списка. После этого мы можем пройтись по массиву в обратном порядке, устанавливая указатели next у каждого узла.
Описание решения
Инициализация массива: Мы создаем пустой массив
nodes
, который будем использовать для хранения всех узлов списка.Заполнение массива: Пройдя по всему списку, мы добавляем каждый узел в массив. В результате массив
nodes
будет содержать все узлы в порядке их появления в списке.Перепривязка указателей: Пройдя по массиву слева направо, начиная со второго элемента, мы устанавливаем для каждого узла
next
указатель на предыдущий элемент в массиве.Обнуление указателя next у первого элемента: Так как первый элемент в массиве (который был последним узлом списка) должен стать последним узлом перевернутого списка, его указатель
next
должен быть установлен вNone
.Возвращаем новый head: В конце мы возвращаем последний элемент массива как новый
head
перевернутого списка.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None: # Если список пуст, возвращаем None
return None
nodes = [] # Массив для хранения узлов
while head:
nodes.append(head) # Добавляем узел в массив
head = head.next # Переходим к следующему узлу
for i in range(1, len(nodes)):
node = nodes[i]
# Устанавливаем указатель next
node.next = nodes[i - 1]
# Устанавливаем None для последнего элемента в перевернутом списке
nodes[0].next = None
return nodes[-1] # Возвращаем новый head
Сложность алгоритма
• По времени: O (n), где n — количество элементов в списке.
• По памяти: O (n), так как мы сохраняем все элементы списка в массив.
Визуализация
Давайте рассмотрим визуализацию работы алгоритма на примере списка 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Инициализация пустого массива nodes:
• Начинаем с пустого массива: nodes = [].
Заполнение массива узлами списка:
• Проходим по исходному списку и добавляем каждый узел в массив:
• После первого шага:
nodes = [1]
(где 1 — это ссылка на узел списка с значением 1)• После второго шага:
nodes = [1, 2]
• После третьего шага:
nodes = [1, 2, 3]
• После четвертого шага:
nodes = [1, 2, 3, 4]
• После пятого шага:
nodes = [1, 2, 3, 4, 5]
Теперь массив nodes содержит ссылки на все узлы списка в исходном порядке.
Перепривязка указателей next:
• Теперь мы идем по массиву, начиная со второго индекса, и для каждого узла устанавливаем его
next
указатель на предыдущий узел в массиве.• Для узла 2 (второго элемента массива):
nodes[1].next = nodes[0]
Новый список:
2 <-> 1
(первый узел все еще ссылается на второй, поэтому связь идет в обе стороны, цикличная связь)• Для узла 3 (третьего элемента массива):
nodes[2].next = nodes[1]
Новый список: 3 → 2 <-> 1
• Для узла 4 (четвертого элемента массива):
nodes[3].next = nodes[2]
Новый список:
4 -> 3 -> 2 <-> 1
• Для узла 5 (пятого элемента массива):
nodes[4].next = nodes[3]
Новый список:
5 -> 4 -> 3 -> 2 <-> 1
В этот момент все узлы, начиная со второго, указывают на предыдущие узлы в новом порядке.
Обнуление указателя next для первого узла массива:
• Поскольку первый элемент массива теперь последний в новом списке, его next указатель должен быть
None
.nodes[0].next = None
Теперь первый узел (бывший 1 → NULL) становится последним:
5 -> 4 -> 3 -> 2 -> 1 -> NULL
.Возвращаем новый head списка:
• Последний элемент массива
nodes[-1]
, который содержит узел с значением5
, теперь становится новымhead
списка.В итоге, исходный список
1 -> 2 -> 3 -> 4 -> 5 -> NULL
превращается в перевернутый список5 -> 4 -> 3 -> 2 -> 1 -> NULL.
2. Решение с использованием метода двух указателей
Подход
Этот алгоритм не требует использования дополнительной памяти, кроме нескольких указателей, что делает его более эффективным по сравнению с методом на основе массива. Идея состоит в том, чтобы постепенно развернуть связи между узлами, проходя по списку один раз.
Алгоритм
Инициализация указателя prev:
Мы начинаем с указателя prev, который изначально равенNone
. Этот указатель будет использоваться для хранения предыдущего узла в перевернутом списке.Проход по списку:
Мы проходим по списку, изменяя указатели next каждого узла, чтобы они указывали на предыдущий узел (
prev
). Для этого в цикле мы выполняем следующие шаги:• Сохраняем указатель на следующий узел (
tmp = head.next
), чтобы не потерять его после измененияhead.next
.• Изменяем текущий указатель
next
узлаhead
, чтобы он указывал наprev
.• Перемещаем
prev
на текущий узел (prev = head
).• Перемещаем
head
на следующий узел (head = tmp
).Возвращаем новый head:
После завершения прохода по списку
prev
будет указывать на последний узел исходного списка, который теперь станетhead
перевернутого списка.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None # Инициализация указателя на предыдущий узел
while head:
tmp = head.next # Сохраняем указатель на следующий узел
head.next = prev # Разворачиваем текущий узел
prev = head # Смещаем указатель prev на текущий узел
head = tmp # Переходим к следующему узлу
return prev # Возвращаем новый head списка
Сложность алгоритма
• По времени: O (n), где n — количество элементов в списке.
• По памяти: O (1), так как используем только два указателя.
Визуализация
Рассмотрим исходный список 1 -> 2 -> 3 -> 4 -> 5 -> NULL
.
Инициализация:
prev = None
,head = 1
.Первый шаг цикла:
•
tmp = 2
(сохраняем следующий узел)•
head.next = None
(разворачиваем указатель1 -> NULL
)•
prev = 1
,head = 2
.Состояние: 1 → NULL, 2 → 3 → 4 → 5 → NULL.
Второй шаг цикла:
•
tmp = 3
(сохраняем следующий узел)•
head.next = 1
(разворачиваем указатель2 -> 1
)•
prev = 2
,head = 3
.Состояние:
2 -> 1 -> NULL
,3 -> 4 -> 5 -> NULL
.Повторяем до конца:
После завершения всех шагов получаем перевернутый список:
5 -> 4 -> 3 -> 2 -> 1 -> NULL
.