Решение задачи с собеседования Reverse Linked List [+ ВИДЕО]24.08.2024 16:45

На видео более подробное объяснение каждого решения

Постановка задачи

Ссылка на задачу: 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.