Где применяется
1. Задача
История кнопки «назад» в браузере, плейлист, цепочка шагов отмены устроены одинаково. Каждый элемент знает только следующий за ним: «потом это, потом это, потом это». Номеров, по которым можно прыгнуть, нет. Чтобы добраться до пятого элемента, идёшь по ссылкам от первого.
Это связный список (linked list), который ты собирал в двух прошлых уроках. Каждый элемент это узел { val, next }: значение и ссылка на следующий узел (у последнего null). Теперь задача: перевернуть всю цепочку. Последний узел должен стать первым, а каждая ссылка должна вести в обратную сторону.
Самый простой способ: скопировать все значения в массив, развернуть массив и собрать цепочку заново. Это работает, но требует второй копии всех данных. Ссылки можно развернуть прямо на месте: один проход по узлам и три переменные.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитreverseList(1 → 2 → 3 → 4 → 5)Все стрелки смотрят вправо. prev начинается с null, curr с головы списка.
Как узнать
Эти слова в условии значат этот паттерн
- развернуть связный список (весь список или между позициями)
- развернуть группами по k
- без дополнительного массива или с O(1) доп. памяти
- поменять местами пары узлов
- односвязный список, доступен только .next
Похоже, но не то
- Слияние и перестройка связного списка (Linked list merge & reorder)
Слияние сплетает два списка в один. Разворот перевязывает один список на месте.
- Быстрый и медленный указатели (Fast & slow pointers)
Та пара находит середину или цикл обходом. Она не меняет ни одной ссылки.
- Стек (LIFO) (Stack (LIFO))
Сложить все узлы в стек и снять их тоже даёт разворот. Это стоит O(n) памяти.
- Рекурсия (Recursion)
Рекурсивный вариант читается хорошо, но тратит n кадров стека. Цикл обходится тремя переменными.
n до 1e6 даёт O(n) времени и O(1) памяти. Рекурсивная форма стоит O(n) стека.
На LeetCode
Задачи, где нужно развернуть связный список целиком, один его кусок или каждый блок из k узлов. Сохрани next, разверни указатель назад и сдвинь prev и curr вперёд.
Это задача урока с теми же тремя указателями.
Дойди до узла перед left, разверни right минус left плюс 1 узлов и заново соедини оба конца.
Разворот блоками по 2, и каждый блок пристёгивается к уже готовой части.
Проверь, что осталось k узлов, разверни их, прицепи блок, а короткий хвост оставь как есть.