Урок

Связные списки

Интуиция: поезд из вагонов

Представь поезд. Каждый вагон знает только следующий вагон за собой: между ними сцепка. Чтобы попасть в пятый вагон, придётся пройти через первые четыре. Зато прицепить новый вагон в середину легко: расцепил два вагона, вставил между ними новый и сцепил заново. Остальной состав при этом не двигается.

Это и есть связный список:

узел (вагон) хранит значение val и ссылку next на следующий узел;
голова (head) — первый узел, через неё мы входим в список;
у последнего узла next = null: дальше ничего нет.

3→7→1→9→null

head указывает на 3, у узла 9 next = null

Чем список отличается от массива

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

Операция	Массив	Связный список
Доступ по индексу `i`	O(1)	O(n): нужно идти от головы
Вставка или удаление, если есть ссылка на соседа	O(n): нужно сдвигать элементы	O(1): перецепляем ссылки
Вставка в начало	O(n)	O(1)
Лишняя память	нет	указатель в каждом узле

Главная мысль: в списке дёшево менять структуру и дорого искать. На собесе почти все задачи на списки сводятся к аккуратной работе со ссылками.

Определение узла

Это определение пригодится в каждой задаче главы:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # значение
        self.next = next    # ссылка на следующий узел

Приём 1. Фиктивная голова (dummy)

Неприятный момент в задачах на списки: голова может измениться. Например, нужно вставить элемент перед первым узлом или удалить сам первый узел. Тогда код начинает обрастать проверками вида if head == null и if вставляем в начало.

Решение — создать фиктивный узел dummy, который стоит перед головой. Теперь у любого настоящего узла есть предыдущий, и все случаи обрабатываются одинаково. В конце возвращаем dummy.next.

Пример: вставим число x в отсортированный список.

def insert_sorted(head, x):
    dummy = ListNode(0, head)        # фиктивный узел перед головой
    prev = dummy
    while prev.next and prev.next.val < x:
        prev = prev.next             # ищем узел, после которого вставлять
    prev.next = ListNode(x, prev.next)
    return dummy.next                # настоящая голова (могла измениться)

Обрати внимание: пустой список и вставка в начало работают без единого лишнего if.

Приём 2. Разворот на месте тремя указателями

Задача: развернуть все стрелки в обратную сторону, не создавая новых узлов.

1→2→3→4→5→null

До: 1 → 2 → 3 → 4 → 5

5→4→3→2→1→null

После: 5 → 4 → 3 → 2 → 1, новая голова — 5

Нам понадобятся три указателя:

prev — уже развёрнутая часть, вначале null;
curr — текущий узел, вначале head;
next — запасная ссылка, чтобы не потерять хвост.

На каждом шаге:

Запомни хвост: next = curr.next.
Разверни стрелку: curr.next = prev.
Сдвинь оба указателя: prev = curr, curr = next.

Когда curr станет null, в prev окажется новая голова. Время O(n), память O(1).

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

Приём 3. Быстрый и медленный указатели

Два указателя стартуют с головы. Медленный (slow) делает 1 шаг, быстрый (fast) делает 2 шага.

Середина списка. Когда fast дойдёт до конца, slow окажется ровно посередине: он прошёл вдвое меньше.

1→2→3→4→5→null

fast дошёл до 5, а slow стоит на середине — 3

Условие цикла: while fast and fast.next. Тогда fast никогда не прыгнет в null.next.

Есть ли цикл. Если хвост списка замкнут на какой-то узел, fast будет бегать по кругу и рано или поздно догонит slow, как бегун на стадионе догоняет пешехода. Встретились — цикл есть. Дошли до null — цикла нет. Время O(n), память O(1), никаких множеств посещённых узлов.

Как это звучит на собесе

«Заведу dummy перед головой, чтобы не обрабатывать отдельно случай, когда меняется первый узел».
«Разворачиваю на месте тремя указателями: O(n) по времени, O(1) по памяти».
«Использую быстрый и медленный указатели: быстрый ходит по два узла, поэтому медленный остановится на середине, а если есть цикл — они встретятся».

Проговаривай граничные случаи вслух: пустой список, один узел, два узла.

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

Потерял хвост. Перезаписал curr.next, не сохранив его. Всегда сначала запоминай next.
Разыменовал null. Написал fast.next.next без проверки fast.next.
Вернул dummy вместо dummy.next.
Сдвинул head и потерял начало списка. Для обхода заводи отдельный указатель.
Забыл про один узел. Проверь, что твой цикл работает на списке [1].

Ты уже знаешь три главных приёма для списков: dummy, разворот и два указателя. Дальше потренируешь их на задачах.