CODEWITHSUNDEEP
c++recursionlinked-list
Ayumu Kasugano
Ayumu Kasugano

Reputation: 440

Deleting a linked list with specified data recursively

I want to delete a linked list recursively. I figured how to do this iteratively but I'm curious on how to do this. So far I have:

void deleteNodeRecursively(LinkedList *list, int value){
  Node *curr=list->head;
  if (list->head==NULL){
    return;
  }

  else if (list->head->data==value){
    Node *x=list->head->next;
    delete list->head;
    list->head=x;
  }
   else{
    LinkedList *newlist;
    newlist->head=list->head->next;
    deleteNodeRecursively(newlist,value);
  }
}

Where I defined

struct LinkedList{
   Node *head;
};

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

I can remove the head if need be, but I can't figure out how to remove the body or tails and then correctly stitch up the list, let alone do it recursively. How do I proceed? Why won't this work?

EDIT: Removed question marks and replaced with code that I thought would work.

Upvotes: 1

Views: 716

Answers (1)

P0W
P0W

Reputation: 47794

Assuming you have a "correct" constructor and destructor for your Node data.

You would have to track address of the deletion, for which you could pass a double pointer or a reference to pointer.

void deleteNodeRecursively(Node** list, int value){
//                             ^^^ double pointer to track address withing recursive call
  Node *curr= *list ; 
  if (curr ==NULL){ // Base case for recursion 
    return;
  }

  else if ( curr->data==value){ // If node to be deleted is found
    *list = curr->next; // Update the address for recursive calls
    delete curr; // Delete this current "got" node
  }

 // Else simple recurse into 
  deleteNodeRecursively( &(*list)->next, value );
}

Note: This implementation will delete all nodes with data that matches value .

Upvotes: 1

Related Questions