Задача №5: Reverse Linked List

Задача обращения односвязного списка является классической задачей в программировании и имеет множество применений. Недавно стала популярной в кругах подготовки к техническим собеседованиям благодаря своей простоте и одновременно важности в понимании работы со связными списками.

В этой статье мы рассмотрим пошаговое решение задачи Reverse Linked List с помощью алгоритма итеративного и рекурсивного обращения.

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

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

Пример 1:

• Ввод: head = [1,2,3,4,5]
• Вывод: [5,4,3,2,1]

Пример 2:

• Ввод: head = [1,2]
• Вывод: [2,1]

Пример 3:

• Ввод: head = []
• Вывод: []

Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
Значения узлов находятся в диапазоне от -5000 до 5000.

Итеративный метод

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev

Давайте теперь разберем код итеративного метода построчно:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:

1. class Solution : Мы определяем класс Solution, который будет содержать решение задачи.
   
   
2. def reverseList(self, head: ListNode) -> ListNode:: Мы определяем метод reverseList, который принимает на вход голову (начало) односвязного списка (head) и возвращает новую голову списка. ListNode здесь предполагается классом, представляющим узлы односвязного списка.

        prev = None
        current = head

3. prev = None: Мы инициализируем переменную prev значением None. Это будет указатель на предыдущий узел, который изначально равен None, так как у первого узла списка нет предыдущего.
   
   
4. current = head Мы инициализируем переменную current значением head. current будет использоваться для перемещения по списку, начиная с головы.

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

5. while current: Мы начинаем цикл while, который будет выполняться до тех пор, пока current не станет равным None, что означает достижение конца списка.
   
   
6. next_node = current.next: Мы сохраняем ссылку на следующий узел в переменной next_node, чтобы не потерять доступ к следующему узлу после изменения ссылки текущего узла.
   
   
7. current.next = prev: Мы изменяем ссылку текущего узла на предыдущий узел. Это осуществляет обращение связи у текущего узла, так что он указывает на предыдущий узел вместо следующего.
   
   
8. prev = current: Мы обновляем переменную prev, чтобы она указывала на текущий узел перед переходом к следующему шагу в списке.
   
   
9. current = next_node: Мы перемещаем указатель current на следующий узел списка.

        return prev

10. return prev: После завершения обхода списка и его обращения мы возвращаем prev, который теперь указывает на новую голову списка, после того как старая голова стала хвостом.

Рекурсивный метод

Рекурсивный подход основан на том, что обращение списка можно представить как обращение “остатка” списка после текущего элемента.

class Solution:
    def reverseList(self, head: ListNode) -> 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

Теперь построчно разберем рекурсивный метод решения этой задачи:

        if not head or not head.next:
            return head

3. if not head or not head.next:: Проверка базового случая рекурсии. Если список пустой (head is None) или содержит только один элемент (head.next is None), то он уже обращен и мы просто возвращаем голову списка.

        reversed_head = self.reverseList(head.next)

4. reversed_head = self.reverseList(head.next): Рекурсивный вызов метода reverseList для обращения “остатка” списка, исключая текущий узел head. reversed_head будет содержать новую голову обращенного “остатка” списка.

        head.next.next = head

5. head.next.next = head: Мы обращаем связь следующего узла текущего узла (head.next) так, чтобы он указывал на текущий узел (head). Это обеспечивает обращение списка.

        head.next = None

6. head.next = None: Мы обнуляем ссылку следующего узла текущего узла (head). Это необходимо, чтобы предотвратить зацикливание списка после его обращения.

        return reversed_head

7. return reversed_head: Возвращаем новую голову обращенного “остатка” списка.

Заключение

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

1. Итеративный метод:
   • Временная сложность: [math]\text{O}(\text{n})[/math]
   • Где [math]\text{n}[/math]- количество узлов в списке.

Этот метод имеет линейную временную сложность, так как проходит по каждому узлу списка только один раз, меняя указатели.

2. Рекурсивный метод:
   • Временная сложность: [math]\text{O}(\text{n})[/math]
   • Где [math]\text{n}[/math] – количество узлов в списке.

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