CODEWITHSUNDEEP
c++memory-managementlinked-list
Jim Khan
Jim Khan

Reputation: 3

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node

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

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

I know that this would be the result

node = 3
deleteNode(node)
1->2->3->4->5
1->2->4->5

but where would this lead to a memory leak, the pointer would point to the new node, but would the int variable 3 still be floating around in memory somewhere? Thank you!

Upvotes: 0

Views: 105

Answers (2)

bobah
bobah

Reputation: 18864

It is impossible to get rid of the node not having a pointer to its predecessor in the slist.

What you can do is move ->data and ->next from the node->next into the node and get rid of the node->next. It will be almost the same as requested — get rid of the data stored in the node->data and make list one element shorter.

The steps:

  1. Dispose of node->data
  2. Save the pointer to the node to be disposed tmp = node->next
  3. Copy the next node stat into the current node node->next = tmp->next; node->data = tmp->data
  4. Dispose of tmp

And the code (have not tried to compile):

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

Upvotes: 0

eerorika
eerorika

Reputation: 238331

but would this lead to a memory leak

Yes.

but would the int variable 3 still be floating around in memory somewhere?

No. The node which contains 4 is the one that is leaked, since it is the node containing 3 which was overwritten, and that is the node which was pointing to 4. The result would be like this:

      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

Upvotes: 1

Related Questions