This question is wrong.You cannot delete the node


  • 30
    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?


  • 0
    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.


Log in to reply
 

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