This question is wrong.You cannot delete the node


  • 36
    L
    post the answer first:
    class Solution {
    public:
        void deleteNode(ListNode* node) {
            node->val = node->next->val;
            node->next = node->next->next;
        }
    };
    

    However, this question is INCORRECT for sure, since you don't really "delete" a node, you are replacing the value. In fact, this is a terrible design leading to memory leaks almost for sure.

    I wonder what company gives such misleading question. It's better called "modify" a node, instead of "deleting". Deleting means free the memory, and the incorrect description will mislead any person with slight experience on C++.


  • 2

    "Deleting means free the memory"

    Then do that?


  • 1
    P

    The question says to delete A node (as in ANY node), not THE node that contains the value. By moving all the values up one in the list, you are able to delete the last node, which is A node. In C++, you use "free". In Java, you let the JVM do the cleanup for you (garbage collection). All languages provide some means of freeing memory. So in response to your complaint, there is nothing wrong with the question. It allows for you to critically think on how to remove ANY node but keep the rest of the values within the list.

    Also, your implementation doesn't delete the last node, therefore it isn't correct. In fact, you're only copying the value of the next node to the current one. If your list looked like 1 -> 2 -> 3 -> 4 -> 5 and you were given the third node with value 3, then you'd end up with a list that looks like 1 -> 2 -> 4 -> 4 -> 5. There needs to be a loop that goes through the rest of the list (copying the next node's value into the current one), then deletes the last node.


  • 3
    K

    I agree with the first paragraph. For example, Java Virtual Machine removes objects that have no reference pointing to them. So by "node.next = node.next.next" you set the reference originally pointing to the next node point somewhere else. Thus now the next node is eligible for garbage collection.

    However, I think this method is correct. Notice that in the question, it says "given only access to that node". You cannot go through the rest of the list. All you can do is to modify the current node(which is the one to delete). Let's say your example, 1->2->3->4->5, after this method, the 3 node becomes 4 and points to 5. It actually copy the 4 node into 3 node and jump the 4 node. I think it is a good method given that we can only access one node.


  • 0
    S

    I don't think we are deleting the last node, we are not moving every node up, but only the node after the one passed as parameter, after that this node will be deleted.


  • 0
    K

    I agree with "given only access to that node". Before deleting, the linked list looked like 1 -> 2 -> 3 ->4 -> 5. After deleting, it looks like 1 ->2 -> 4 ->5 and a new linked list unused looks like 4 -> 5.


  • 0
    T

    Actually it is okay to say "delete a node". For example, in Python the node will be recycled because of the reference numbers drops to 0, without waiting for the trigger of GC functions.


  • 0
    S

    How do you delete last node of the linked list?
    Just making the last node as null doesn't work.

    Any suggestions would be highly appreciated.


  • 0
    G

    class Solution {
    public:
    void deleteNode(ListNode* node) {
    ListNode* del = node->next;
    node->val = del->val;
    node->next = del->next;
    free(del);//just do it ,we actually delete the node
    }
    };


  • 0
    M

    @Gy_Hui Nonsense. (Edit: this referred to their original del = NULL before they changed it to free(del)) (And code not formatted properly.)


  • 0
    G

    @ManuelP said in This question is wrong.You cannot delete the node:

    Utter nonsense. (And code not formatted properly.)

    what?you just make the point NULL is delete the node OK?what's wrong?


  • 0
    G

    @ManuelP
    I just think what the author said is wrong


  • 0
    M

    (Edit: Again, this refers to their original del = NULL before they changed it to free(del))

    @Gy_Hui That does not delete the node. You're just setting your local variable to NULL, which does absolutely nothing whatsoever at all to the list. Also, you don't even get to that point, because del->val crashes, because del already is a null pointer. And even if you did get that far, setting it to NULL would be nonsense because it already is a null pointer. (oops, confused this with the topic of deleting the last node.)

    Btw, use nullptr instead of NULL. Also, you're leaking memory.


  • 0
    G

    @ManuelP OK ,we can free(del) to release the node’s memory,right?I just use del=NULL represent free.


  • 0
    M

    @Gy_Hui said in This question is wrong.You cannot delete the node:

    I just use del=NULL represent free.

    Well that's not what it does.

    free(del) might work, but I think it's way more likely that delete del is the correct way.

    (Though I take back the "utter" and parts of my previous comment, as I confused this topic with another one. Sorry about that.)


  • 0
    S

    I think you can handle memory leak by yourself.

    class Solution {
    public:
        void deleteNode(ListNode* node) {
            node->val = node->next->val;
            ListNode* cur = node->next;
            node->next = node->next->next;
            delete cur;
            cur = nullptr;
        }
    };
    

    Then, there would be no memory leak.


  • 0
    M

    @sijiec said in This question is wrong.You cannot delete the node:

    cur = nullptr;

    What do you think that achieves?


  • 1
    S

    @ManuelP
    Setting cur points to nullptr makes sure it didn't point to a value object. If we only delete the object, but not set cur to nullptr, it is possible cause some strange error in a program. For example, this memory store some new value, and the cur still can change the value. However, this kind of problem might happen in big program. For small one, it maybe doesn't matter. Anyway, I think after delete it is a good habit to set the pointer to be nullptr.


  • 0
    M

    @sijiec Ah, ok. In this particular case I think it doesn't do anything (since the variable is immediately lost anyway), but I can imagine the general habit to make sense.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.