Напишите функцию для удаления узла (кроме хвоста) в односвязном списке, предоставляя только доступ к этому узлу

Question

struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

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

Я знаю, что это будет результат

узел = 3
deleteNode (узел)
1-> 2-> 3-> 4-> 5
1-> 2-> 4-> 5

но где это приведет к утечке памяти, указатель будет указывать на новый узел, но будет ли переменная int 3 все еще где-то перемещаться в памяти?Спасибо!

Answer 1

но не приведет ли это к утечке памяти

Да.

но будет ли переменная int 3 все еще где-то перемещаться в памяти?

Нет.Узел, который содержит 4, является утечкой, поскольку это узел, содержащий 3, который был перезаписан, и это узел, который указывал на 4. Результат будет выглядеть следующим образом:

      4  <--- this is the node which was leaked (since nothing points to it)
       \
        ->5
       /
1->2->4  <--- this is the node that used to contain 3

Answer 2

Невозможно избавиться от узла, не имеющего указателя на предшественника в списке.

Что вы можете сделать, это переместить ->data и ->next из node->next в node и избавиться от node->next.Это будет почти так же, как запрошено - избавьтесь от данных, хранящихся в node->data, и сделайте список на один элемент короче.

Шаги:

1. Утилизация node->data
2. Сохранить указатель на подлежащий удалению узел tmp = node->next
3. Скопировать следующую статистику узла в текущий узел node->next = tmp->next; node->data = tmp->data
4. Удалить tmp

И код (не пытался скомпилировать):

node->val = 42; // dispose of node own data (not required for RAII fields)
ListNode* tmp = node->next;
*(node) = *(node->next);
delete tmp;