Help with recursion and linked list

[smesj]

Hey guys, I'm stuck... I am trying to write a function that recursively deletes elements from a list with odd numbers

//remove nodes containing odd values from a sequence of nodes
//Pre: cur is a reference to a Node
//Post: the sequence of nodes starting with cur has had all nodes containing
//      odd values removed
//Return: a reference to the modified sequence of nodes.
Node *removeOdds(Node *cur){

Node *temp;
if (cur == NULL){
    return NULL;
}
else if(cur->data%2 != 0){
    cout << "is odd" << endl;
    temp = cur->next;
    delete cur;
    cur = temp;
    temp->next = removeOdds(cur->next);
    //return cur;
    //return temp;
}
else{
    cout << "is even" << endl;
    cur->next = removeOdds(cur->next);
    return cur;
}
}

This code always crashes... i have some commented out lines that i have attempted but to no avail. ANY help would be appreciated.

[Naughty Albatross]

Hi,

==>

Node* removeOdds(Node *cur)
{
    if (!cur) return NULL;
    if(cur->data%2 == 0)
    {
        cout << "is even" << endl;
        removeOdds(cur->next); return NULL;
    }
    cout << "is odd" << endl;
 
    Node *t = cur->next;
    Node *p = cur->prev;
    Note *r = NULL;
    if(p) { p->next = t; r = p; } else r = t;
    delete cur;
    cur = t;
    if(cur != NULL)
    removeOdds(cur);
    return r;
}

Note that the function almost always returns nothing. Don't try dereferencing the return value if it is NULL!

[Naughty Albatross]

Does that help? :)

[Naughty Albatross]

Edit : Changed my solution, so that it can have a return value.

[smesj]

Kind of! In this case I want this function to return a reference to the head of the single linked list

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

so that i can reprint it to the console and show that i have deleted the nodes containing odd data. This is my testing code (the other function calls work as they are supposed to)

  cout << "testing with a sequence of mixed even/odd numbers:" << endl;
  int input3[] = {2,7,5,32,40,1};
  head = arrayToNodeSequence(input3, 6);
  cout << "full sequence of nodes:" << endl;
  printNodes(head);
  head = removeOdds(head);////////////////////
  cout << "now with odds removed: (only the even values should remain)" << endl;
  printNodes(head);
  deallocateNodeSequence(head);

[Arslan7041]

Must it be recursive? This would be far easier if done iteratively.

[cire]

In the code in the OP, line 17 is not correct.

cur already points to what cur->next would've been on function entry, and it may have the value of nullptr, so dereferencing it would cause undefined behavior.

Line 17 should be return removeOdds(cur); or alternately replace cur with temp since they both point to the same thing.

How I would've written it:

Node* removeOdds(Node* first) {
    if (!first) return nullptr;         // done

    if (first->data % 2 == 0)           // even
    {
        first->next = removeOdds(first->next);
        return first;
    }
    
    auto next = first->next;            // odd
    delete first;                       
    return removeOdds(next);
}

[smesj]

Yea Arslan its for an assignment on recursion so I'm forced to use it.

Sorry 5a8 That still wants a node struct with a previous element. Im subject to the one provided.

cire!!!! That line 17 fix did it. wow I was so close

Thanks so much you guys/gals!! your all awesome.