Answer: Lists

Question: Write a recursive function to delete all the occurrences of a given key key in a singly-linked list and return the head of the new list. The function should have the prototype

ListNode *deleteOccurrences(ListNode *head, int key);

Answer: With recursion:

ListNode*
deleteOccurences(ListNode *head, int key) {
    if(head == NULL) {
        return NULL;
    } else if(key == head->data) {
        ListNode *ret = deleteOccurrences(head->next, key);
        delete head;
        return ret;
    } else {
        head->next = deleteOccurrences(head->next, key);
        return head;
    }
}

ListNode*
deleteOccurences(ListNode *head, int key) {
    ListNode *ret = head;
    ListNode *n = head;
    ListNode *prev = NULL;

    while(n) {
        if(n->data == key) {
            ListNode *next = n->next;
            delete n;
            if(prev == NULL) ret = next;
            else prev->next = next;
            n = next;
        } else {
            prev = n;
            n = n->next;
        }
    }

    return ret;
}