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

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

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

Ссылка на задачу: https://leetcode.com/problems/reverse-linked-list

Дан указатель head на начало односвязного списка, необходимо развернуть список и вернуть развернутый список.

1. Решение с использованием массива

Одним из способов решения этой задачи является использование массива для хранения всех узлов списка. После этого мы можем пройтись по массиву в обратном порядке, устанавливая указатели next у каждого узла.

Описание решения

1. Инициализация массива: Мы создаем пустой массив nodes, который будем использовать для хранения всех узлов списка.

2. Заполнение массива: Пройдя по всему списку, мы добавляем каждый узел в массив. В результате массив nodes будет содержать все узлы в порядке их появления в списке.

3. Перепривязка указателей: Пройдя по массиву слева направо, начиная со второго элемента, мы устанавливаем для каждого узла next указатель на предыдущий элемент в массиве.

4. Обнуление указателя next у первого элемента: Так как первый элемент в массиве (который был последним узлом списка) должен стать последним узлом перевернутого списка, его указатель next должен быть установлен в None.

5. Возвращаем новый 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

1. Инициализация пустого массива nodes:

   • Начинаем с пустого массива: nodes = [].

2. Заполнение массива узлами списка:

   • Проходим по исходному списку и добавляем каждый узел в массив:

   • После первого шага: nodes = [1] (где 1 — это ссылка на узел списка с значением 1)

   • После второго шага: nodes = [1, 2]

   • После третьего шага: nodes = [1, 2, 3]

   • После четвертого шага: nodes = [1, 2, 3, 4]

   • После пятого шага: nodes = [1, 2, 3, 4, 5]

   Теперь массив nodes содержит ссылки на все узлы списка в исходном порядке.

3. Перепривязка указателей 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

   В этот момент все узлы, начиная со второго, указывают на предыдущие узлы в новом порядке.

4. Обнуление указателя next для первого узла массива:

   • Поскольку первый элемент массива теперь последний в новом списке, его next указатель должен быть None.
   nodes[0].next = None

   Теперь первый узел (бывший 1 -> NULL) становится последним: 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

5. Возвращаем новый head списка:

   • Последний элемент массива nodes[-1], который содержит узел с значением 5, теперь становится новым head списка.

   В итоге, исходный список 1 -> 2 -> 3 -> 4 -> 5 -> NULL превращается в перевернутый список 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

2. Решение с использованием метода двух указателей

Подход

Этот алгоритм не требует использования дополнительной памяти, кроме нескольких указателей, что делает его более эффективным по сравнению с методом на основе массива. Идея состоит в том, чтобы постепенно развернуть связи между узлами, проходя по списку один раз.

Алгоритм

1. Инициализация указателя prev:
   Мы начинаем с указателя prev, который изначально равен None. Этот указатель будет использоваться для хранения предыдущего узла в перевернутом списке.

2. Проход по списку:

   Мы проходим по списку, изменяя указатели next каждого узла, чтобы они указывали на предыдущий узел (prev). Для этого в цикле мы выполняем следующие шаги:

   • Сохраняем указатель на следующий узел (tmp = head.next), чтобы не потерять его после изменения head.next.

   • Изменяем текущий указатель next узла head, чтобы он указывал на prev.

   • Перемещаем prev на текущий узел (prev = head).

   • Перемещаем head на следующий узел (head = tmp).

3. Возвращаем новый 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.

1. Инициализация:

   prev = None, head = 1.

2. Первый шаг цикла:

   • tmp = 2 (сохраняем следующий узел)

   • head.next = None (разворачиваем указатель 1 -> NULL)

   • prev = 1, head = 2.

   Состояние: 1 -> NULL, 2 -> 3 -> 4 -> 5 -> NULL.

3. Второй шаг цикла:

   • tmp = 3 (сохраняем следующий узел)

   • head.next = 1 (разворачиваем указатель 2 -> 1)

   • prev = 2, head = 3.

   Состояние: 2 -> 1 -> NULL, 3 -> 4 -> 5 -> NULL.

4. Повторяем до конца:

   После завершения всех шагов получаем перевернутый список: 5 -> 4 -> 3 -> 2 -> 1 -> NULL.