Simple and elegant solution in C++


  • 31
    E
    ListNode *removeElements(ListNode *head, int val)
    {
        ListNode **list = &head;
    
        while (*list != nullptr)
        {
            if ((*list)->val == val)
            {
                *list = (*list)->next;
            }
            else
            {
                list = &(*list)->next;
            }
        }
    
        return head;
    }
    

    Original recursive version:

    void removeHelper(ListNode *&head, int val)
    {
        if (head == nullptr)
        {
            return;
        }
        else if (head->val == val)
        {
            head = head->next;
        }
        else
        {
            removeHelper(head->next, val);
        }
    }

  • 9
    D

    You could also delete the element being removed in order to not leak memory.


  • 1
    Y

    could you just briefly explain why it works? it seems that head will change when *list = (*list)->next executed


  • 0
    E

    It is originally a recursive function (I've added the code in my original post). Because it is a tail recursion, I can convert it to a loop, which is my final answer.


  • 1

  • 0
    W

    In the recursive version,is the node that passed over deleted?Is there a safe problem?
    In the two star version,the node is overwritten,so it equals deleted?


  • 1
    E

    No, the node is not deleted because I don't know how the node is allocated. If it's allocated by new operator, I shall use delete operator; if it's allocated using malloc(), I shall call free() to free the memory; or maybe the memory is managed by some other object, then I should't delete it at all.


  • 0
    _

    pointer to pointer, cool~


  • 0
    O

    Brilliant!!!


  • 0
    S

    @efanzh
    really like the recursive solution:
    however, I guess I did not really know how to use removeHelper(), I have to add a line

        else if (head->val == val)
        {
            head = head->next;
            removeHelper(head, val); // I have to add this line, please correct me if I am wrong, any help is appreciated
        }
    

    again really nice solution, Thx

    and when I use the removerhelp fn, I just used:

        ListNode* removeElements(ListNode* head, int val) {
            // ListNode * ret=head;
            removeHelper(head,val);
            return head;
        }
    

    I do not understand that when return head will still give me the whole linked list.
    Cause if remove head, no problem.
    if not head, then your new variable is head->next


  • 0

    I don't think this program should delete node being removed since the deleted node's location is unknown.
    My two line code:


    ListNode* removeElements(ListNode* head, int val)
    {
    for (ListNode **curr = &head; *curr; (*curr)->val == val ? *curr = (*curr)->next : *(curr = &(*curr)->next));
    return head;
    }


  • 0
    W

    SUCK MY BIG CHINESE COCK!!!!!!!


Log in to reply
 

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