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

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

Переворот связного списка — одна из классических задач, проверяющих понимание работы с указателями и манипуляцией структурами данных. Решение требует изменения направления связей между узлами.

Подход 1: Итеративное решение (Iterative Reversal)

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

Алгоритм:

• Используем три указателя: prev, current и next
• На каждом шаге сохраняем следующий узел
• Переворачиваем стрелку текущего узла на предыдущий
• Двигаемся дальше по списку

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

def reverseList(head):
    prev = None
    current = head
    
    while current:
        # Сохраняем следующий узел
        next_node = current.next
        
        # Переворачиваем связь
        current.next = prev
        
        # Двигаемся дальше
        prev = current
        current = next_node
    
    return prev

Сложность:

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

Подход 2: Рекурсивное решение

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

def reverseListRecursive(head):
    # Базовый случай: пустой список или один узел
    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) — из-за стека вызовов

Пример использования

# Создаём список: 1 → 2 → 3 → 4 → 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Переворачиваем
reversed_head = reverseList(head)

# Проверяем результат
current = reversed_head
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")
# Вывод: 5 -> 4 -> 3 -> 2 -> 1 -> None

Когда какой подход использовать

Используй итеративное решение когда:

• Нужна максимальная производительность
• Важна пространственная сложность O(1)
• Работаешь с очень большими списками

Используй рекурсивное решение когда:

• Код должен быть максимально читаемым
• Размер входных данных небольшой
• Готов к overhead памяти на стек

Практические применения

Переворот списков используется в:

• Проверке палиндромов в связных списках
• Обращении очередей в некоторых алгоритмах
• Преобразовании структур данных перед сортировкой
• Обработке потоков данных в реальном времени

Типичные ошибки

❌ Потеря ссылки на следующий узел — обязательно сохрани его в переменную перед изменением

❌ Забывают установить head.next = None в рекурсивном решении

❌ Off-by-one ошибки в условии цикла