Thread: Linked Lists : removeduplicate(); problem.

Hi,

I'm doing the linked list excercises from http://cslibrary.stanford.edu/105/. Currently I'm on #10, removeduplcate();. It takes a linked list that is sorted and then removes all duplicates. I've written some code and doodled on paper how it should work, however, it keeps going on in an infinte loop, somewhere, and I'm not sure where =P Here's the code. I've ommited the parts that don't have any use.

Code:

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

Code:

void Push(struct Node **Head, int data){
     struct Node * NewNode = new Node;                 // Makes a new node and a pointer 'NewNode' to it
     NewNode->data = data;
     NewNode->next = *Head;                            // Sets the next field to point at what headpointer is pointing at
     *Head = NewNode;                                  // Copies the pointer of NewNode to HeadPointer
}

Code:

void Read(struct Node * HeadPointer){
     struct Node * Current = HeadPointer;    
     cout<<"[ ";            
     while(Current != NULL){
                   cout<<Current->data;
                   if( Current->next != NULL)          // Checks to see that if there is a node after the current node
                       cout<<" , ";
                   Current = Current->next;
                   }
     cout<<" ]"<<endl;
}

Code:

void RemoveDuplicate(struct Node * HeadPointer){
    if(HeadPointer !=NULL){                            // Only work if the list isn't empty.
         struct Node * Current = HeadPointer;
         struct Node * NextNode;
         struct Node * Temp;
         while(Current->next != NULL){                 // Cycle through the list...
         NextNode = Current->next;
                  while(NextNode->data == Current->data){
                                       Temp = NextNode;     // Temp will hold the "middle node"
                                       NextNode = NextNode->next;   // Advance nextnode to the third node..
                                       delete Temp;     // Delete the middle node
                  }
         Current->next = NextNode;                      // Link the first node to the third node
         }
    }
}

The error is somewhere in the above code ^

Code:

 
int main(){
   struct Node* Nodelist  = NULL;      
Push(&Nodelist, 3);Push(&Nodelist, 2); Push(&Nodelist, 2); Push(&Nodelist, 1); Push(&Nodelist, 1);
    Read(Nodelist);       
    RemoveDuplicate(Nodelist);
    Read(Nodelist);
}

The program goes off in an infinate loop somewhere in the middle of Remove Duplicate. I'm not sure where, however :|

Thanks,
Inside

the inner while loop can crash because Current can become NULL. Test it out on paper with a list containing all duplicates.

Code:

void RemoveDuplicate(struct Node * HeadPointer){
     if(HeadPointer != NULL){                          // Only work if we have something to check for
                    struct Node * Previous;            // Create the pointers
                    struct Node * Current = HeadPointer;
                    struct Node * Temp;
                    Previous = Current;                // Previous will point to the "original" node to check against. The
                    Current = Current->next;           // node after it willl be deleted if it's the same as the original
                    while(Current != NULL){            
                                  if( Current->data == Previous->data){ // If two nodes next to each other are the same
                                      Temp = Current;  // Set temp to point at the second copy..
                                      Current = Current->next; // Advance current to point to the third node
                                      delete Temp;     // delete the copy (middle node)
                                      Previous->next = Current; // Connect the first node to the third node
                                  }
                                  else{                // if two adjoining nodes aren't the same..
                                      Previous = Current;  // Advance the previous pointer...
                                      Current = Current->next; // Advance current
                                  }
                    }
     }
}

Yeah, that's what I ended up doing.. it.. *seems* to work ok...