Подготовка к алгоритмическим задачам
Задачи на связные списки на собеседовании: разбор типовых
Коротко
| Задача | Приём | Сложность |
|---|---|---|
| Развернуть список | три указателя | O(n), O(1) |
| Найти цикл | быстрый и медленный | O(n), O(1) |
| Середина списка | быстрый и медленный | O(n), O(1) |
| N-й с конца | два указателя с отступом | O(n), O(1) |
| Слить отсортированные | фиктивный узел | O(n+m), O(1) |
Тема простая по идеям, но требует аккуратности: почти все ошибки здесь — потерянные указатели, а не неверный алгоритм.
Два приёма, которые закрывают почти всё
Фиктивный узел
Заводим пустой узел перед головой. Тогда операции с первым элементом ничем не отличаются от операций с остальными, и половина проверок на None исчезает.
dummy = ListNode(0, head) # ... работаем ... return dummy.next
Применяйте всегда, когда голова списка может измениться. Это не украшательство — это то, что отличает чистое решение от каши из условий.
Быстрый и медленный указатели
Один идёт на шаг, другой на два. Даёт середину списка, обнаружение цикла и N-й элемент с конца.
Разворот списка
Задача номер один по частоте. Должна писаться без раздумий.
def reverse_list(head): prev = None current = head while current: nxt = current.next # сохраняем следующий current.next = prev # разворачиваем ссылку prev = current # сдвигаем prev current = nxt # сдвигаем current return prev # prev — новая голова
Порядок четырёх строк критичен. Если сначала написать current.next = prev, вы потеряете доступ к остатку списка. Сохранение nxt первым — обязательно.
Полезно нарисовать три узла со стрелками и пройти цикл руками. На интервью это тоже стоит сделать вслух.
Рекурсивный вариант короче, но расходует O(n) стека:
def reverse_recursive(head): if not head or not head.next: return head new_head = reverse_recursive(head.next) head.next.next = head head.next = None return new_head
Упомяните оба и обоснуйте выбор итеративного: на списке из 10⁵ узлов рекурсия упадёт.
Обнаружение цикла
Алгоритм Флойда, он же «черепаха и заяц».
def has_cycle(head) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False
Почему работает: если цикл есть, быстрый указатель рано или поздно догонит медленный — на каждом шаге расстояние между ними внутри цикла сокращается на единицу.
Условие while fast and fast.next проверяет обе ссылки: без второй проверки fast.next.next упадёт на списке чётной длины.
Найти начало цикла
Продолжение, которое спрашивают следом.
def detect_cycle_start(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast:
Решай алгоритмические задачи как профи
# второй указатель от головы, оба по шагу
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
Математика: если до начала цикла `a` шагов, а точка встречи находится в `b` шагах внутри цикла, то расстояние от точки встречи до начала цикла равно `a`. Отсюда — пустить один указатель от головы, второй от точки встречи, и они сойдутся в начале цикла.
Это стоит уметь объяснить: вопрос «а почему это работает?» задают почти всегда.
## Середина списка
```python
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Когда быстрый дошёл до конца, медленный на середине. При чётной длине возвращается второй из двух средних — уточните у интервьюера, какой нужен.
N-й узел с конца
def remove_nth_from_end(head, n: int): dummy = ListNode(0, head) fast = slow = dummy for _ in range(n): fast = fast.next # отступ в n шагов while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next # пропускаем нужный узел return dummy.next
Фиктивный узел здесь спасает случай, когда удаляется голова. Без него понадобилась бы отдельная ветка.
Слияние двух отсортированных списков
def merge_two_lists(l1, l2): dummy = ListNode(0) tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 or l2 # прицепляем остаток return dummy.next
Строка tail.next = l1 or l2 — идиома: один из списков уже пуст, прицепляем непустой остаток целиком.
Условие <= вместо < сохраняет устойчивость: равные элементы остаются в порядке первого списка.
Другие задачи, которые встречаются
Проверить палиндромность списка. Найти середину, развернуть вторую половину, сравнить. O(n) времени, O(1) памяти — комбинация двух базовых приёмов.
Удалить дубликаты из отсортированного списка. Один проход, пропускаем равные соседние.
Пересечение двух списков. Два указателя, при достижении конца переходят на голову другого списка — сойдутся в точке пересечения.
Сложить два числа, представленных списками. Проход с переносом, аккуратно с последним переносом.
Все они собираются из фиктивного узла и двух указателей.
Частые ошибки
Потеря указателя. Забыли сохранить next перед изменением. Симптом — список обрывается или зацикливается.
Проверка только fast. Нужно while fast and fast.next — иначе падение на чётной длине.
Отсутствие фиктивного узла там, где голова может измениться. Приводит к разрастанию кода проверками.
Сравнение по значению вместо ссылки. В обнаружении цикла нужно slow is fast, а не slow.val == fast.val — значения могут совпасть у разных узлов.
Забытый случай пустого списка. head может быть None, и первое же обращение упадёт.
Практический совет
Рисуйте. Три квадратика и стрелки на бумаге экономят полчаса отладки в голове. На интервью это нормально и даже приветствуется — видно, что вы работаете со структурой, а не угадываете.
И проверяйте решение руками на списке из двух узлов. Большинство ошибок с указателями вылезают именно там.
Что запомнить
- Фиктивный узел применяйте всегда, когда голова может измениться.
- В развороте списка сохраняйте
nextдо изменения ссылки. - Быстрый и медленный указатели дают середину, цикл и N-й с конца.
- Проверяйте
fast and fast.next, иначе падение на чётной длине. - Сравнивайте узлы по ссылке (
is), а не по значению. - Рисуйте на бумаге — здесь это экономит больше всего времени.