Разверните односвязный список: верните голову списка, в котором узлы идут в обратном порядке. Решите итеративно, без дополнительной памяти.
Короткий ответ
- Три указателя: prev, current и сохранённый next
- На каждом шаге стрелка current.next разворачивается на prev
- Сохранить next до перезаписи, иначе хвост потерян
- Сдвигаем prev и current на шаг вперёд
- Когда current стал None, prev — новая голова
- Итеративно O(n) времени и O(1) памяти, рекурсия тратит стек
Итеративный разворот тремя указателями работает за O(n) по времени и O(1) по дополнительной памяти.
Как сказать вслух
пример ответаЯ иду по списку и у каждого узла разворачиваю указатель next назад, на предыдущий узел. Чтобы не потерять остаток списка, перед перезаписью сохраняю ссылку на следующий узел. Когда дохожу до конца, предыдущий узел и есть новая голова.
Подробный ответ
Основной ответ
Держим два указателя: prev (изначально None) и current (голова). В цикле, пока current не None: сохраняем nxt = current.next, разворачиваем current.next = prev, затем сдвигаемся — prev = current, current = nxt. По завершении prev указывает на бывший хвост, который стал головой. Один проход — O(n) времени, O(1) дополнительной памяти, список модифицируется на месте. Рекурсивный вариант изящен (развернуть хвост, прицепить голову в конец), но тратит O(n) стека и падает на длинных списках. Полезно проговорить инварианты: в любой момент prev — голова уже развёрнутой части, current — голова ещё не тронутой. Пустой список и список из одного узла обрабатываются циклом без специальных веток.
Ключевые моменты
- Порядок присваиваний. Сохранить next до перезаписи current.next — единственное место, где теряют остаток списка.
- Инвариант цикла. Prev всегда возглавляет развёрнутый префикс, current — неразвёрнутый суффикс; доказательство корректности в одну строку.
- Итерация против рекурсии. Рекурсия тратит O(n) стека вызовов; на собеседовании начинайте с итеративного O(1) по памяти.
- Граничные случаи. None и один узел проходят без веток: цикл не выполнится или выполнится один раз.
Практический контекст
Задача-индикатор уверенной работы с указателями: интервьюер смотрит, нарисуете ли вы схему на доске и не запутаетесь ли в порядке присваиваний. Частые развития: развернуть подсписок с позиции m по n, развернуть группами по k, проверить список на палиндром через разворот половины. Отрепетируйте решение до автоматизма — его часто дают как разминку с ограничением по времени.
Пример кода
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def reverse_list(head):
prev = None
while head:
nxt = head.next # сохранить остаток
head.next = prev # развернуть стрелку
prev, head = head, nxt
return prev
head = Node(1, Node(2, Node(3)))
r = reverse_list(head)
out = []
while r:
out.append(r.val)
r = r.next
assert out == [3, 2, 1]Частые ошибки
- Перезаписывают current.next до сохранения следующего узла и теряют хвост списка
- Возвращают current (он None после цикла) вместо prev
- Пишут рекурсию и не могут назвать её расход памяти на стек