Skip to content

Linked lists

Связные списки (Linked Lists) — это линейная структура данных, где элементы хранятся не в последовательных ячейках памяти (как в массивах), а в виде узлов, связанных ссылками. Это позволяет эффективно вставлять и удалять элементы, но усложняет доступ к ним по индексу.

Устройство узла ListNode#

На LeetCode связный список обычно определяется классом ListNode, где каждый объект хранит значение и ссылку на следующий объект.
Если ссылка next указывает на None, это означает, что узел является последним в списке.

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

Основные операции и их сложность#

Связные списки сильно отличаются от массивов по производительности операций, что важно учитывать при выборе структуры в задачах.
В отличие от массивов, здесь нельзя получить доступ к элементу по индексу за O(1), так как нужно физически пройти от головы списка до нужной позиции

Операция Связный список (Singly) Массив (Array/List)
Доступ по индексу O(n) O(1)
Вставка в начало O(1) O(n) (нужен сдвиг)
Удаление (зная узел) O(1) O(n)
Поиск элемента O(n) O(n)

Техника Dummy Node (Фиктивный узел)#

Одна из самых полезных техник на LeetCode — создание пустого начального узла перед «головой» списка.
Это избавляет от написания множества проверок if head is None или специальных условий для изменения первого элемента.

    # Создаем фиктивный узел, который стоит перед реальным списком
    dummy = ListNode(0)
    current = dummy

    # Пример: добавляем элементы в новый список
    for i in range(1, 4):
        current.next = ListNode(i)
        current = current.next

    # Результат: dummy(0) -> 1 -> 2 -> 3
    # Настоящий список начинается с dummy.next
    head = dummy.next

Метод двух указателей (Fast & Slow)#

Для решения задач часто используется паттерн «быстрого и медленного» указателей, когда один (fast) идет в два раза быстрее другого (slow).

Эта техника позволяет найти середину списка за один проход или определить наличие цикла (петли) в структуре.​​

  • Поиск середины: когда fast доходит до конца, slow оказывается ровно посередине.​​
  • Поиск цикла: если список зациклен, то через некоторое время fast догонит slow (алгоритм «заяц и черепаха»).​​
  • Удаление N-го узла с конца: если fast опережает slow на NN шагов, то когда fast достигнет конца, slow будет указывать на нужный элемент.​

Практические советы для LeetCode#

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

Самые частые ошибки — это AttributeError: 'NoneType' object has no attribute 'next', которые возникают, когда вы пытаетесь обратиться к следующему узлу у последнего элемента списка.

Всегда проверяйте текущий узел и его поле next в условии цикла while current and current.next.