I'm trying to delete every node at positions divisible by 5. With my approach I cannot seem to delete the last node:

void removeDivFive(Node* head){
    int count = 0;
    Node* temp = head;
    
    while(temp != NULL){
        count  ;
        if(count%5==0){
            if(temp->next != NULL){
                temp->value = temp->next->value;
                temp->next = temp->next->next;
            }
        }
        temp = temp->next;
    }
    
    while(head != NULL){
        cout<<head->value;
        head = head->next;
    }
}

What I'm doing is copying the value of the next node to the current one and changing the pointer to the next next node. By doing this I cannot delete the last node if the list has 10 nodes.

Any help would be appreciated

CodePudding user response：

First off, you are leaking the nodes you "remove". You need to actually destroy them since they are no longer being used.

Now, regarding your actual problem - what do you thing temp->next points at when the last node in the list is at a position divisible by 5? NOTHING! Thus, if (temp->next != NULL) evaluates as false, so you aren't even attempting to do anything with that last node, you just skip past it, which is why you are not removing it.

For every 5th node, you are copying the value of the next node into the current node, and then pointing the current node to skip the next node. In other words, you are not removing the 5th, 10th, 15th, etc nodes at all. You are actually removing the 6th, 11th, 16th, etc nodes instead. You need to remove the current node instead of the next node.

Which also means, you need to keep track of the previous node in the list so that you can re-link its next pointer to point at the next node that follows the current node being removed.

Try something more like this instead:

void removeDivFive(Node* head){
    int count = 0;
    Node *temp = head, *prev = NULL, *next;
    
    while (temp != NULL){
          count;
        next = temp->next;
        if ((count % 5) == 0){
            if (prev != NULL) {
                prev->next = next;
            }
            delete temp;
        }
        else {
            prev = temp;
        }
        temp = next;
    }
}

Online Demo

Alternatively (as described by @GoswinvonBrederlow in comments):

void removeDivFive(Node* head){
    int count = 0;
    Node *temp = head, *next;
 
    while (temp != NULL){
          count;
        if ((count  %4) == 0){
            if (temp->next != NULL){
                next = temp->next->next;
                delete temp->next;
                temp->next = next;
            }
        }
        temp = temp->next;
    }
}

Online Demo

CodePudding user response：

As mentioned in the comments the deleted node isn't counted. So you need to delete a node every 4 counts instead of every 5. And if you use count%4 == 0 then the first time temp will point at node 4 and you want to delete the 5th node. So no need for temp->value = temp->next->value;, just remove the next node. Then next time around when count = 8 then temp will point at node 9. So again temp->next is the node to remove. ...

So the condition always fires for the node before the 5th, which is perfect for removing it.

void removeDivFive(Node* head){
    int count = 0;
    for (Node* temp = head; temp != NULL; temp = temp->next) {
        count  ;
        if(count%4==0){
            if(temp->next != NULL){
                Node *t = temp->next;
                temp->next = t->next;
                delete t;
            }
        }
    }
    
    while(head != NULL){
        cout<<head->value;
        head = head->next;
    }
}