CODEWITHSUNDEEP
c++recursionlinked-list
Felix Chang
Felix Chang

Reputation: 9

Recursive Linked List Difference

I just got this question from text book, but I just can't seem to figure it out what the answer is. The question asks "Explain in one sentence what the function does, and what is 'bad' about this function?" (It does not have to do with programming style).

And by the way, what's the difference between "return f(x, p->next)" and "p->next = f(x, p->next)" ? I just can't seem to figure out the difference between these two.

struct Node {
    int data;
    Node* next;
};

Node* f(int x, Node* p) {
    if (p == nullptr) {
        return nullptr;
    }
    else if (p->data == x) {
        return f(x, p->next);
    }
    else {
        p->next = f(x, p->next);
        return p;
    }
}

Upvotes: 0

Views: 64

Answers (1)

Jack Deeth
Jack Deeth

Reputation: 3357

What f does is walk through the linked list, removing any elements which hold the value x.

else if (p->data == x) { // if the next element has our target value
    return f(x, p->next); // make that element's next element, become our own next element
}

What's bad about it is that std::vector exists, and while

vec.erase(std::remove(vec.begin(), vec.end(), x), vec.end());

isn't the most elegant line of code, it's a heck of a lot more comprehendable and recognisable than recursive pointer functions.

Also f leaks memory. The removed element doesn't get deleted; f just overwrites the pointer which knows where it is.

Upvotes: 2

Related Questions