Объясни разворот списка
Вопрос
Объясни, как развернуть односвязный список, и какая сложность у итеративной и рекурсивной версии.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Три указателя: prev, curr, next
Порядок: сохранить next, перевесить ссылку, сдвинуть prev и curr
Новая голова это prev после цикла
Итеративно O(n) времени и O(1) памяти
Рекурсивно O(n) памяти на стек
Что могут спросить следом
- Как развернуть только часть списка от m до n?
- Как развернуть группами по k?
- Чем опасна рекурсия на длинном списке?
Разбор
Держу три ссылки: prev изначально null, curr на голову и временную next. На каждом шаге сначала запоминаю curr.next, иначе потеряю хвост, затем перевешиваю curr.next на prev, потом сдвигаю prev на curr и curr на сохранённый next. Когда curr станет null, prev указывает на бывший последний узел, это новая голова. Каждый узел обрабатывается один раз: O(n) времени и O(1) памяти. Рекурсивная версия разворачивает хвост и цепляет текущий узел в конец, она короче, но держит n кадров на стеке, на длинном списке это O(n) памяти и риск переполнения стека.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.