Linked Lists : removeduplicate(); problem.

This is a discussion on Linked Lists : removeduplicate(); problem. within the C++ Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    6

    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

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    6
    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:
    Last edited by InsideTheAsylum; 03-03-2005 at 04:23 PM.

  3. #3
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    the inner while loop can crash because Current can become NULL. Test it out on paper with a list containing all duplicates.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    6
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  2. Question On Linked Lists
    By Zildjian in forum C Programming
    Replies: 8
    Last Post: 10-23-2003, 11:57 AM
  3. Linked lists
    By sballew in forum C Programming
    Replies: 6
    Last Post: 10-24-2001, 08:52 PM
  4. I need some help on my linked lists app
    By valar_king in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2001, 08:36 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21