--- title: "Разворот связного списка: три указателя, код на Python и четыре задачи вокруг" url: https://algopath.pro/ru/blog/razvorot-svyaznogo-spiska language: ru summary: "Сохранить, перевязать, сдвинуть. Итеративный и рекурсивный код на Python, разворот части списка, Palindrome Linked List, Reorder List и типичные ошибки." updated: 2026-11-05 --- # Разворот связного списка: три указателя, код на 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. Это единственная сложная строка в нём. Отработать узнавание приёма можно на странице [разворот связного списка](/ru/patterns/linked-list-reversal). Поиск середины разобран на странице [быстрый и медленный указатели](/ru/patterns/fast-slow-pointers). ## Вопросы и ответы ### Зачем нужна фиктивная голова? Чтобы у первого узла тоже был предыдущий. Тогда разворот с первой позиции ничем не отличается от разворота из середины. ### Как развернуть двусвязный список? У каждого узла поменять местами prev и next. Один проход, никаких дополнительных указателей. ### Можно ли развернуть список через массив? Да: собрать значения, развернуть, записать обратно. Это O(n) памяти. На собеседовании такой ответ принимают как запасной, а потом просят O(1). ### Где приём встречается в реальных системах? В отмене действий, где история хранится списком и её проходят назад. В сборщиках мусора при переворачивании указателей во время обхода. В реализации стека поверх списка.