Разворот связного списка: три указателя, код на Python и четыре задачи вокруг

Короткий ответ. Разворот связного списка делается за один проход. Нужны три указателя: prev, cur и next. На каждом шаге текущий узел перевязывается назад, и все три сдвигаются вперёд. Время O(n), память O(1). Приём лежит в основе задач Palindrome Linked List и Reorder List. Ниже шаги, код на Python, разбор и типичные ошибки.

Что такое разворот связного списка?

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

Создавать новый список нельзя, если просят O(1) памяти. Нужно перевязать существующие ссылки.

Трудность одна: перевязав ссылку, вы теряете доступ к остатку списка. Поэтому остаток сохраняют в третий указатель до перевязки.

Массив развернуть проще: там есть индексы, и можно менять местами края. В списке индексов нет, есть только ссылки вперёд. Отсюда и весь приём с тремя указателями.

Как разворот связного списка работает по шагам?

• prev = None, cur = head.
• Сохраняем next = cur.next, иначе остаток потеряется.
• Перевязываем: cur.next = prev.
• Сдвигаем: prev = cur, cur = next.
• cur стал None, prev это новая голова.

Порядок строк важен. Сначала сохранить, потом перевязать, потом сдвинуть.

Цикл делает n шагов, по одному на узел. Ни один узел не создаётся и не удаляется. Поэтому память O(1) при любой длине списка.

Как это выглядит на примере?

Список 1, 2, 3. prev пустой, cur на 1. Сохраняем next на 2. 1 теперь ссылается на пустоту. prev на 1, cur на 2.

Сохраняем next на 3. 2 ссылается на 1. prev на 2, cur на 3. Сохраняем next, он пустой. 3 ссылается на 2. prev на 3, cur пустой. Новая голова 3, список 3, 2, 1.

Как написать разворот связного списка на Python?

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

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next          # сохранить остаток
        cur.next = prev         # перевязать
        prev, cur = cur, nxt    # сдвинуть
    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

def reverse_between(head, left, right):
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    cur = before.next
    for _ in range(right - left):   # каждый шаг переносит следующий узел вперёд
        moved = cur.next
        cur.next = moved.next
        moved.next = before.next
        before.next = moved
    return dummy.next

Итеративный вариант основной. Рекурсивный короче в объяснении. Но он стоит O(n) стека и падает на длинном списке.

Чем задачи на разворот отличаются друг от друга?

Задача	Что разворачиваем	Добавка к базовому коду
Reverse Linked List	Весь список	Ничего
Reverse Linked List II	Узлы с left по right	Фиктивная голова и узел before
Reverse Nodes in k-Group	Каждые k узлов	Проверка, что осталось k, и сшивка групп
Palindrome Linked List	Вторую половину	Середина через быстрый и медленный указатели
Reorder List	Вторую половину	Слияние двух половин через одну

Как решить Palindrome Linked List?

Нужно проверить, читается ли список одинаково в обе стороны, за O(1) памяти. Находим середину быстрым и медленным указателями. Разворачиваем вторую половину. Идём двумя указателями от головы и от новой головы половины и сравниваем.

Хороший тон: развернуть половину обратно перед выходом. Входные данные остаются нетронутыми.

Как решить Reorder List?

Список из пяти узлов 1..5 надо превратить в 1, 5, 2, 4, 3. Три шага: найти середину, развернуть вторую половину, слить две половины по очереди. Каждый шаг O(n), память O(1).

Как решить Reverse Nodes in k-Group?

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

Фиктивная голова упрощает первую группу. Указатель на хвост предыдущей группы двигается после каждого разворота.

По каким словам в задаче узнать приём?

• «Развернуть список», «развернуть часть списка».
• «Проверить палиндром» на списке.
• «Переставить узлы» без создания новых.
• «O(1) дополнительной памяти» рядом со словом «список».

На каких ошибках ломается разворот?

• Перевязывают cur.next до того, как сохранили остаток. Список обрывается.
• Возвращают head вместо prev. Старая голова теперь хвост.
• В Reverse Linked List II забывают фиктивную голову. Случай left = 1 ломается.
• В k-Group разворачивают неполную последнюю группу, хотя условие велит оставить её.

Как объяснить приём на собеседовании?

Назовите три указателя и порядок «сохранить, перевязать, сдвинуть». Нарисуйте три узла и покажите один шаг. Назовите O(n) и O(1).

Спросят рекурсивный вариант, скажите про строку head.next.next = head. Это единственная сложная строка в нём.

Отработать узнавание приёма можно на странице разворот связного списка. Поиск середины разобран на странице быстрый и медленный указатели.

Вопросы и ответы

Зачем нужна фиктивная голова?

Чтобы у первого узла тоже был предыдущий. Тогда разворот с первой позиции ничем не отличается от разворота из середины.

Как развернуть двусвязный список?

У каждого узла поменять местами prev и next. Один проход, никаких дополнительных указателей.

Можно ли развернуть список через массив?

Да: собрать значения, развернуть, записать обратно. Это O(n) памяти. На собеседовании такой ответ принимают как запасной, а потом просят O(1).

Где приём встречается в реальных системах?

В отмене действий, где история хранится списком и её проходят назад. В сборщиках мусора при переворачивании указателей во время обхода. В реализации стека поверх списка.