JuniorКодОчень частоЕщё не отвечали
Напишите функцию, которая разворачивает односвязный список
Дана голова односвязного списка из Node. Разверните список «на месте» (in-place) и верните новую голову.
Требования:
- O(n) время, O(1) доп. память (итеративно; не копируйте значения в массив).
- Обработайте пустой список и список из одного элемента.
struct Node {
int val;
Node* next;
};
Node* reverseList(Node* head) {
// ваш код здесь
}Допишите реализацию.
Используйте три указателя: prev (изначально nullptr), curr и next. На каждом шаге: сохраните next, направьте curr->next на prev, продвиньте prev к curr, продвиньте curr к сохранённому next. Когда curr равен nullptr, prev — новая голова. Время O(n), память O(1).
- ✗Потерять следующий узел до перезаписи curr->next — всегда сохраняйте
next = curr->nextпервым - ✗Возвращать curr вместо prev в конце — curr равен nullptr при выходе из цикла
- ✗Не обрабатывать крайние случаи: пустой список или список из одного элемента
- →Как развернуть двусвязный список?
- →Как развернуть только подотрезок [m, n] связного списка?
Оглавление
Задача
Дана структура односвязного списка. Напишите функцию, которая разворачивает список «на месте» (in-place) и возвращает новую голову.
Решение
#include <cassert>
#include <initializer_list>
struct Node {
int val;
Node* next;
};
// --- Итеративное решение — O(n) время, O(1) память ---
Node* reverseList(Node* head) {
Node* prev = nullptr;
Node* curr = head;
while (curr) {
Node* next = curr->next; // 1. сохраняем следующий
curr->next = prev; // 2. разворачиваем ссылку
prev = curr; // 3. продвигаем prev
curr = next; // 4. продвигаем curr
}
return prev; // prev — новая голова
}
// --- Рекурсивное решение (для иллюстрации, O(n) стека) ---
Node* reverseListRec(Node* head) {
if (!head || !head->next) return head;
Node* newHead = reverseListRec(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
// Вспомогательные функции для тестов
Node* makeList(std::initializer_list<int> vals) {
Node* head = nullptr;
Node** cur = &head;
for (int v : vals) { *cur = new Node{v, nullptr}; cur = &(*cur)->next; }
return head;
}
int nthVal(Node* head, int n) {
while (n--) head = head->next;
return head->val;
}
int main() {
Node* list = makeList({1, 2, 3, 4, 5});
list = reverseList(list);
assert(nthVal(list, 0) == 5);
assert(nthVal(list, 4) == 1);
// Edge cases
assert(reverseList(nullptr) == nullptr);
Node* single = new Node{42, nullptr};
assert(reverseList(single)->val == 42);
}Ключевые моменты
- Итеративный вариант использует O(1) памяти — предпочтителен на практике.
- Порядок операций критичен: сначала сохраняем
next, затем разворачиваем указатель. - Рекурсия читаема, но может вызвать stack overflow на больших списках.
Оглавление
