Python: от основ до собеседования и работы / Алгоритмы и структуры данных для собеседований / урок 77 из 99

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

⏱ 45 мин · 🧩 заданий: 5

Устройство

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

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

    def __repr__(self):
        return f"ListNode({self.val})"

head = ListNode(1, ListNode(2, ListNode(3)))     # 1 → 2 → 3 → None

node = head
while node:                                      # обход — O(n)
    print(node.val, "→", node.next)
    node = node.next

Пройдите пример 👣 Пошагово: визуализатор нарисует узлы в памяти и стрелки-ссылки между ними.

head │ ▼ ┌───┬───┐ ┌───┬───┐ ┌───┬──────┐ │ 1 │ ●─┼──▶ │ 2 │ ●─┼──▶ │ 3 │ None │ └───┴───┘ └───┴───┘ └───┴──────┘
Операция Связный список Массив (list)
доступ по индексу O(n) O(1)
вставка/удаление в начале O(1) O(n)
вставка/удаление по ссылке на узел O(1) (двусвязный) O(n)
поиск O(n) O(n)
память + ссылка на каждый узел компактно, дружит с кешем процессора

В Python связные списки на практике почти не пишут (есть list и deque), но на собеседованиях это одна из любимых тем: задачи проверяют аккуратную работу с указателями.

Приём 1: фиктивный узел

Многие крайние случаи (пустой список, удаление головы) исчезают, если завести «фиктивный» узел перед головой:

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

def build(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head

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

def remove_all(head, target):
    dummy = ListNode(0, head)              # не нужно отдельно обрабатывать голову
    node = dummy
    while node.next:
        if node.next.val == target:
            node.next = node.next.next     # «перешагнуть» узел
        else:
            node = node.next
    return dummy.next

print(to_list(remove_all(build([7, 7, 1, 7, 2, 7]), 7)))

Приём 2: разворот

Три указателя: предыдущий, текущий, следующий. Это задача номер один про списки.

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

def build(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head

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

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

def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head        # следующий узел теперь указывает на нас
    head.next = None
    return new_head

print(to_list(reverse(build([1, 2, 3, 4]))))
print(to_list(reverse_recursive(build([1, 2, 3, 4]))))

Нарисуйте стрелки на бумаге — это лучший способ не запутаться. Рекурсивный вариант тратит O(n) стека.

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

slow идёт на 1 шаг, fast — на 2.

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

def build(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow.val               # когда fast в конце, slow — в середине

print(middle(build([1, 2, 3, 4, 5])), middle(build([1, 2, 3, 4, 5, 6])))

def cycle_start(head):
    """Алгоритм Флойда: есть ли цикл и где он начинается."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                     # встретились внутри цикла
            slow = head
            while slow is not fast:          # идём с одинаковой скоростью — встретимся в начале цикла
                slow, fast = slow.next, fast.next
            return slow.val
    return None

nodes = [ListNode(i) for i in range(6)]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
nodes[-1].next = nodes[2]                    # 0 → 1 → 2 → 3 → 4 → 5 → (снова 2)
print("цикл начинается в узле", cycle_start(nodes[0]))

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

Приём 4: слияние

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

def build(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head

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

def merge(a, b):
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b                   # прицепить остаток
    return dummy.next

print(to_list(merge(build([1, 4, 7]), build([2, 3, 8, 9]))))

Комбинация приёмов: палиндром = найти середину + развернуть вторую половину + сравнить; сортировка списка = середина + рекурсия + слияние (merge sort за O(n log n)).

Двусвязный список

У узла есть и next, и prev — удаление узла по ссылке за O(1). Используется в LRU-кеше (вместе со словарём) и внутри collections.deque (там узлы — блоки по 64 элемента).

class Node:
    def __init__(self, key, value):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    """LRU-кеш без OrderedDict: словарь + двусвязный список со стражами."""
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(None, None), Node(None, None)   # фиктивные концы
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(cache.get("b"), cache.get("a"), cache.get("c"))

Как решать задачи на списки

1) Нарисуйте 3–4 узла и стрелки. 2) Подумайте о крайних случаях: пустой список, один узел, два узла, изменение головы. 3) Используйте фиктивный узел. 4) Перед node.next = ... сохраните то, что потеряете.

Итог

  • Связный список: O(1) вставка/удаление по ссылке, O(n) доступ по индексу.
  • Фиктивный узел убирает особые случаи с головой.
  • Разворот — три указателя prev, current, next.
  • Быстрый/медленный указатели: середина, цикл и его начало (Флойд), n-й с конца.
  • Слияние отсортированных списков; двусвязный список + словарь = LRU-кеш.

Практика решено 0 из 5

Вы не вошли — ответы проверяются, но прогресс не сохранится. Войти или зарегистрироваться.
Задание 1 Программа на Python

Разворот списка. Разверните односвязный список и верните новую голову. Итеративно, O(n) времени, O(1) памяти. Класс ListNode и помощники build/to_list уже есть.

Какие тесты проверяют код (3) 
assert to_list(reverse(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert reverse(None) is None and to_list(reverse(build([7]))) == [7]
nodes = build([1, 2, 3]); first = nodes; new_head = reverse(nodes); assert first.next is None and new_head.next.next is first, "Разворачивайте сами узлы, а не создавайте новые"
Задание 2 Программа на Python

Слияние двух отсортированных списков. Слейте два отсортированных связных списка в один отсортированный (из тех же узлов) и верните голову. Используйте фиктивный узел.

Какие тесты проверяют код (3) 
assert to_list(merge_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert merge_lists(None, None) is None and to_list(merge_lists(None, build([0]))) == [0]
assert to_list(merge_lists(build([5, 6]), build([1, 2, 3]))) == [1, 2, 3, 5, 6]
Задание 3 Программа на Python

Цикл в списке. Определите, есть ли в связном списке цикл, за O(1) памяти (алгоритм Флойда: «черепаха и заяц»). Без множеств и словарей.

Какие тесты проверяют код (4) 
a, b, c, d = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
a.next, b.next, c.next, d.next = b, c, d, b
assert has_cycle(a) is True

a, b = ListNode(1), ListNode(2)
a.next = b
assert has_cycle(a) is False and has_cycle(None) is False

a = ListNode(1); a.next = a
assert has_cycle(a) is True

import inspect; src = inspect.getsource(has_cycle); assert "set(" not in src and "{}" not in src and "dict(" not in src, "Решите за O(1) памяти — двумя указателями"
Задание 4 Программа на Python

Удалить n-й узел с конца за один проход. Верните голову списка. [1, 2, 3, 4, 5], n = 2 → [1, 2, 3, 5]. Подсказка: фиктивный узел и два указателя на расстоянии n.

Какие тесты проверяют код (3) 
assert to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert remove_nth_from_end(build([1]), 1) is None and to_list(remove_nth_from_end(build([1, 2]), 2)) == [2]
assert to_list(remove_nth_from_end(build([1, 2]), 1)) == [1]
Задание 5 Заполнить таблицу

Сложность операции: связный список против массива (list)

O(1) у обоихбыстрее у связного спискабыстрее у массива
доступ к i-му элементу
вставка в начало
удаление узла, на который уже есть ссылка (двусвязный)
добавление в конец (с указателем на хвост / list.append)
перебор всех элементов (с учётом кеша процессора)
Отметьте ячейку — «+», пустая — «−».

Войдите, чтобы отмечать пройденные уроки.