должны ли мы беспокоиться о возможных перезаписях при удалении классической структуры узла после копирования узла?

Question

https://leetcode.com/problems/delete-node-in-a-linked-list/description/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

Постановка задачи: Учитывая связанный список размером не менее 2, вам дается указатель на один из узлов (гарантированно не являющийся хвостом).Удалить узел.

Связанный список [1,2,3,4], ввод: 2, правильный вывод: [1,3,4]

void deleteNode(ListNode* node) {
    ListNode* next = node->next;
    *node = *(node->next);
    delete next;
}

Выше приведено правильное решение,Тем не менее, я думаю, что это не должно быть правильно.

Причина: во 2-й строке функции вы копируете значение / содержимое всего узла.Таким образом, вы в конечном итоге копируете значение int, а также адрес следующего узла (т. Е. Указатель следующего узла).

Однако в 3-й и последней строке функции вы в конечном итоге удалите следующий (что эквивалентно node-> next).

Если в будущем вы выделите достаточно ресурсов, это не вызовет проблем с перезаписью?Насколько я понимаю, следующий указатель теперь содержит адресное пространство чего-то, что было только что удалено.

Если я ошибаюсь в своем понимании, я был бы очень признателен, если бы кто-то меня поправил.

Answer 1

Это верно, разыменование ячейки памяти node, на которую указывает указатель, - это неопределенное поведение.Стоит отметить, что delete на самом деле не обнуляет память, потому что это лишняя работа, а C ++ не выполняет ничего, что явно не требуется.

int* x = new int;
*x = 5;
int* y = x;
delete x;
std::cout << *y << std::endl; // This outputs 5 on my machine (on release config)

Что скорее происходит, так это то, что диспетчер памяти в ОС помечает эти места как свободные, и они могут занять позже.Возможно, нет.Пока эта память не будет перезаписана, она вернет правильное значение.Но опять же, это UB, и никакой производственный код не должен иметь его.

Имейте в виду, что иногда среда выполнения c ++ может обнулять память после освобождения, например, при компиляции с флагами отладки.

Answer 2

Давайте исследуем функцию шаг за шагом:

ListNode* next = node->next;

Здесь вы копируете next данного узла во временный указатель, пока что все хорошо.например, если у вас было {1, 2, 3, 4} и вы дали второй узел этой функции, теперь next равен 3, а это третий элемент.

 *node = *(node->next);

Скопируйте содержимое следующего узла в узел, как вы упомянули,также скопируйте это рядом с этим.Продолжая данный пример, теперь у вас есть {1, 3, 3, 4}, которые как 3 (второй и третий элементы следующие 4 (четвертый элемент)).

delete next;

Удалить далее.Теперь, учитывая прошлый пример, то, что вы делаете здесь, удаляет второй 3 (третий элемент).и ваш результат будет {1, 3, 4}.

Этот метод не удаляет конкретный заданный узел (я имею в виду, что он не удаляет данный указатель), но копирует его в следующий, затем удаляет следующий, и он работает как задумано.