Deleting a node in circular linked list

Question

I have a basic linked list problem that I have attempted to solve below. I would appreciate any inputs on my approach, correctness of the algorithm (and even coding style). The problem calls for a function that deletes all occurrences of an int in a circular linked list and returns any node from the list or NULL (when the list is null).

Here's some C++ code that I have so far:

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

Node* deleteNode(Node* &node, int num){

    if(!node){
        return NULL;
    }

    Node* given = node;
    Node* del;

    while(node->next != given){
        if(node->next->data == num){
            del = node->next;
            node->next = node->next->next;
            delete del;
        }
        node = node->next;
    }

    //Check if the first node needs to be deleted, with variable node pointing to last element
    if(given->data == num){
        node->next = given->next;
        delete given;
    }

    return node;
}

Answer 1

The delete node; should be delete del;.

Also, use Node* node as parameter, instead of Node* &node which will prevent non-lvalues from passing in.

p.s. Forgot a semicolon after struct definition? :)

Answer 2

Without following all your logic I can see at a glance this code cannot work.

You are checking for the input list being empty and that's the only case in which your code returns NULL. But what happens if you are passed a list in which all elements must be deleted?

This problem also has a subtlety in it. To check if you completed a circular list you need to compare to the first address to see if you got linked back to the start. However if this element has been deleted then by C++ standard you're not even allowed to use its address in a comparison.

To avoid making two passes over the elements to be deleted one possible trick is to "break the loop" when starting iteration so you can check for NULL instead of checking for the address of the starting node.