Связный список: разворот

Разворот связного списка — почти ритуал собеседований; разберём его до автоматизма.

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

Что такое узел

В отличие от массива, элементы списка не лежат подряд в памяти — они связаны ссылками. Доступ по индексу здесь O(n), зато вставка/удаление в известном месте — O(1).

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

def build(values):
    head = None
    for v in reversed(values):
        node = Node(v)
        node.next = head
        head = node
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

lst = build([1, 2, 3, 4])
print(to_list(lst))

Вывод:

[1, 2, 3, 4]

Классическая задача: развернуть список

Нужно перевернуть направление всех ссылок: голова станет хвостом. Идём по списку, на каждом шаге перенаправляя next текущего узла на предыдущий. Храним три указателя: prev, cur и сохранённый next.

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

def build(values):
    head = None
    for v in reversed(values):
        node = Node(v)
        node.next = head
        head = node
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next   # запомнить следующий
        cur.next = prev  # развернуть ссылку
        prev = cur       # сдвинуть prev
        cur = nxt        # сдвинуть cur
    return prev

lst = build([1, 2, 3, 4, 5])
print(to_list(reverse(lst)))

Вывод:

[5, 4, 3, 2, 1]

Как работает под капотом

Критичен порядок присваиваний. Если развернуть cur.next = prev до того, как мы сохранили nxt = cur.next, мы потеряем доступ к остатку списка — связь оборвётся. Поэтому сначала запоминаем следующий узел, потом разворачиваем ссылку, потом сдвигаем оба указателя. В конце cur стал None, а prev указывает на бывший хвост — это новая голова. Время O(n), память O(1): мы не создаём новых узлов.

Частые ошибки

• Перенаправить cur.next = prev до сохранения nxt — потеря хвоста списка.
• Вернуть head вместо prev — вернёте старую (теперь последнюю) голову.
• Забыть случай пустого списка: цикл просто не выполнится и вернёт None — это корректно.

Итог

• Список — это узлы со ссылками; доступ по индексу O(n), вставка O(1).
• Разворот: три указателя prev/cur/nxt, строгий порядок присваиваний.
• O(n) время, O(1) память; новая голова — это prev в конце цикла.