# Linked Lists : removeduplicate(); problem.

• 03-03-2005
InsideTheAsylum
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
• 03-03-2005
InsideTheAsylum
Oops, I think I see the error...

I have
NextNode = Current->next;
Current->next = NextNode;

That doesn't look like it does anything special.. Oops.

Edit: Fiddled with the function so that it looks like

Code:

```void RemoveDuplicate(struct Node * HeadPointer){     if(HeadPointer !=NULL){                            // Only work if the list isn't empty.         struct Node * Current = HeadPointer;         struct Node * Previous;         struct Node * Temp;         while(Current != NULL){                 Previous = Current;                 Current = Current->next;                 while(Current->data == Previous->data){                                     Temp = Current;                                     Current = Current->next;                                     delete Temp;                                     Previous->next = Current;                 }         }     } }```
But hey, guess it what, it doesn't work D:
• 03-04-2005
skorman00
the inner while loop can crash because Current can become NULL. Test it out on paper with a list containing all duplicates.
• 03-04-2005
InsideTheAsylum
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...