CODEWITHSUNDEEP
c++linked-list
WombatCombat
WombatCombat

Reputation: 51

Deleting every other node of a linked list

I searched previous asked questions but could not find exactly what I was looking for. I was curious if anyone had any idea on how to delete every other node of a linked list. I have a function called duplicate which take 1 2 3 and turns it into 1 1 2 2 3 3. Deleting every other node would work just fine, no need to compare them or anything. If anyone has any insights. Please don't just post source code.

Heres what I was trying to do but wasn't working.

Node *current;
Node *undo;
for (current = front, undo = current->next->next; 
undo != NULL; current = current->next, undo = current->next->next){
    current->next = undo;
}

This will output 1 1 2 2 3 3 3

Thank you for any help. I can comment back later to clarify any misconceptions.

Upvotes: 0

Views: 1214

Answers (2)

sj0h
sj0h

Reputation: 912

Original code:

for (current = front, undo = current->next->next; 
   undo != NULL; 
   current = current->next, // this moves current on before you use it's next pointer
   undo = current->next->next){
     current->next = undo;
}

To fix, without deallocating the unwanted nodes (assumes an even number of nodes):

for (current = front;  current != NULL; current = current->next){
      current->next = current->next->next
}

To handle odd length lists, and delete memory of removed nodes:

for (current = front;  current && current->next ; current = current->next){
      undo = current->next;
      current->next = current->next->next
      delete undo;
}

Upvotes: 1

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

I would use std::list (or perhaps std::forward_list if so needed) and std::copy_if or std::remove_if in C++11.

Otherwise, remember the address of the pointer to be modified, something like:

Node**undoad = &front;
int cnt=0;
for (current=front; current != NULL; current=current->next) {
  if (cnt%2 == 1) {
    Node*undo = *undoad;
    undoad = &current->next; 
    if (undo) undo->next = current->next;
  }
  cnt++;
}

However, the above probably is a memory leak: you may need to use delete somewhere.

Upvotes: 0

Related Questions