Разберите фрагмент кода на C: "struct Node* reverse(struct Node* head) { struct Node *prev = NULL, *curr = head; while (curr != NULL) { curr->next = prev; prev = curr; curr = curr->next; } return prev; }" — найдите и объясните ошибку, предложите исправление и оцените сложность алгоритма
Разберите фрагмент кода на C: "struct Node* reverse(struct Node* head) { struct Node *prev = NULL, *curr = head; while (curr != NULL) { curr->next = prev; prev = curr; curr = curr->next; } return prev; }" — найдите и объясните ошибку, предложите исправление и оцените сложность алгоритма
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
curr->next = prev;
далее делается
curr = curr->next;
но после первого присваивания `curr->next` уже указывает на `prev`, поэтому `curr` перейдёт назад (в `prev`) и цикл бесконечно будет идти по уже обработанным узлам.
Исправление: сохранить следующий узел перед переназначением `next`. Правильный код:
struct Node* reverse(struct Node* head) {
struct Node *prev = NULL, *curr = head;
while (curr != NULL) {
struct Node *next = curr->next; // сохранить следующий узел
curr->next = prev;
prev = curr;
curr = next; // перейти на сохранённый следующий
}
return prev;
}
Краткое объяснение: для каждого узла сохраняем указатель на следующий, затем переворачиваем ссылку `next`, сдвигаем `prev` на текущий и `curr` на сохранённый следующий — так мы не теряем доступ к оставшейся части списка.
Сложность: время O(n)\mathcal{O}(n)O(n), память дополнительная O(1)\mathcal{O}(1)O(1) (где nnn — число узлов списка).