Question

Assume you are in main.cpp define a function that is NOT SCOPED to any class. It is NOT a member of the ListInterface nor LinkedList classes. Your function should accept two lists. You will remove all values from the first list that are present in the second list. Example:

Lists before call:                                    Lists after call:

target: A, B, C, A, D, C, E, F, B, C, A                  target: A, A, D, E, F, A

toRemove: C, B, Q, Z                                   toRemove: C, B, Q, Z

template <typename T>

void removeHelper(ListInterface &target, const ListInterface&toRemove)

{

//your code below

Answer 1

Here's the definition of the function removeHelper(): (in C++)

Assumption: Since no info is given in the problem regarding ListInterface, I've assumed that it's a struct of below type for simplicity purpose (you can modify according to your needs):

template<typename T>
struct ListInterface
{
    T val;
    ListInterface *next;
};

removeHelper()'s definition:

template<typename T>
void removeHelper(ListInterface<T> &target, const ListInterface<T> &toRemove) {
    
    // hashmap (using this would tell us if a value in the target list is present in toRemove list or not in O(1) time)
    unordered_map<T, int> toBeRemoved;

    ListInterface<T> prev = NULL, save;

    // assumption: val is the data item of type T (for generalising purpose)  & next is the pointer pointing to the next node in the list

    // adding all the values to be removed into the hashmap
    while (toRemove) {
        toBeRemoved[toRemove -> val] = 1;
        toRemove = toRemove -> next;
    }

    // iterate through target list
    while (target) {

        // if the current value in target is one of the values in the map then remove it
        if (toBeRemoved[target -> val]) {
            
            // if previous node exists
            if (prev)
                prev -> next = target -> next;

            // delete the current node
            save = target;
            target = target -> next;
            save -> next = NULL;
            delete save;
            continue;
        }

        // update prev and target pointers
        prev = target;
        target = target -> next;
    }


}

Hope this helps. For any doubt, please reach out, I'd be happy to help :)

If it worked for you, please give an upvote for this answer, I'd appreciate that! :)

Cheers!