Переворот связного списка

Решение: Переворот связного списка

Это классическая задача на работу со связными списками. Существует несколько подходов: итеративный (в один проход) и рекурсивный. Итеративный подход более эффективен по памяти.

Алгоритм итеративного решения

1. Инициализируем три указателя:
   • prev = None (предыдущий узел)
   • current = head (текущий узел)
   • next_temp = None (для хранения следующего узла)
2. Проходим по всему списку:
   • Сохраняем следующий узел в next_temp
   • Разворачиваем связь: current.next = prev
   • Двигаем prev на текущий узел
   • Двигаем current на следующий узел
3. Возвращаем prev (он будет новым head)

Структура узла

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Реализация (итеративный подход)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head
    
    while current:
        # Сохраняем следующий узел перед изменением связи
        next_temp = current.next
        
        # Разворачиваем связь
        current.next = prev
        
        # Двигаем указатели на один шаг вперёд
        prev = current
        current = next_temp
    
    # prev теперь указывает на новый head
    return prev

Пошаговая визуализация

Исходный список: 1 -> 2 -> 3 -> 4 -> 5

Шаг 0 (начальное состояние):

prev = None
current = 1

Шаг 1:

next_temp = 2
1.next = None
prev = 1, current = 2
Результат: None <- 1    2 -> 3 -> 4 -> 5

Шаг 2:

next_temp = 3
2.next = 1
prev = 2, current = 3
Результат: None <- 1 <- 2    3 -> 4 -> 5

Шаг 3:

next_temp = 4
3.next = 2
prev = 3, current = 4
Результат: None <- 1 <- 2 <- 3    4 -> 5

Шаг 4:

next_temp = 5
4.next = 3
prev = 4, current = 5
Результат: None <- 1 <- 2 <- 3 <- 4    5

Шаг 5:

next_temp = None
5.next = 4
prev = 5, current = None
Результат: None <- 1 <- 2 <- 3 <- 4 <- 5

Возвращаем prev (узел 5) — он становится новым head.

Выход: 5 -> 4 -> 3 -> 2 -> 1 ✓

Рекурсивный подход

def reverseListRecursive(head: ListNode) -> ListNode:
    # Базовый случай: пустой список или один элемент
    if not head or not head.next:
        return head
    
    # Рекурсивно разворачиваем остаток списка
    new_head = reverseListRecursive(head.next)
    
    # Разворачиваем связь для текущего узла
    head.next.next = head
    head.next = None
    
    return new_head

Сложность рекурсивного подхода:

• Временная: O(n)
• Пространственная: O(n) из-за стека вызовов

Вспомогательные функции для тестирования

def create_list(values: list) -> ListNode:
    """Создаёт связный список из массива"""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def list_to_array(head: ListNode) -> list:
    """Преобразует связный список в массив"""
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# Тесты
head = create_list([1, 2, 3, 4, 5])
reversed_head = reverseList(head)
print(list_to_array(reversed_head))  # [5, 4, 3, 2, 1]

# Граничные случаи
print(list_to_array(reverseList(create_list([]))))  # []
print(list_to_array(reverseList(create_list([1]))))  # [1]
print(list_to_array(reverseList(create_list([1, 2]))))  # [2, 1]

Сложность оптимального решения

• Временная сложность: O(n), где n — количество узлов
• Пространственная сложность: O(1), используется только три указателя

Сравнение подходов

Важные детали

• Сохранение next_temp — критично, иначе потеряем ссылку на следующий узел
• Инициализация prev = None — новый конец списка должен указывать на None
• Возврат prev — не head! head станет концом списка

Итеративный подход рекомендуется в production-коде благодаря лучшей производительности по памяти.