Deleteing Duplicate Nodes in a Linked List

[twillie]

Hello,

I have a linked list in C++ and I am trying to remove all duplicate nodes from the list. The code below is what our prof. wrote on the board in pusdo code in class, yet it doesn't seem to be working correctly for me. I also need to preface that the list is not sorted. Prior to entering this part of the code we need to link two preexising lists together. The directions do not say to sort the two list once they are put together.

Any advice would be helpful.

Thanks

r = first;
    while ( r != nil )
    {
        target = (*r).info;
 
        q = r;
        p = (*q).next;
 
        while ( ((*p).next != nil) )
        {
 
            if ( target == (*p).info )
            {
                (*q).next = (*p).next;
            }
            else
            {
                q = p;
                p = (*p).next;
            }//end if
        }//end while
 
        r = (*r).next;
    }
 

[ilikepython]

Hello,

I have a linked list in C++ and I am trying to remove all duplicate nodes from the list. The code below is what our prof. wrote on the board in class, yet it doesn't seem to be working correctly for me. Any advice would be helpful.

Thanks

r = first;
    while ( r != nil )
    {
        target = (*r).info;
 
        q = r;
        p = (*q).next;
 
        while ( ((*p).next != nil) )
        {
 
            if ( target == (*p).info )
            {
                (*q).next = (*p).next;
            }
            else
            {
                q = p;
                p = (*p).next;
            }//end if
        }//end while
 
        r = (*r).next;
    }
 

Have you declared nil? Usually you check like this:

while (r != NULL);
 

[JosAH]

Hello,

I have a linked list in C++ and I am trying to remove all duplicate nodes from the list. The code below is what our prof. wrote on the board in pusdo code in class, yet it doesn't seem to be working correctly for me. I also need to preface that the list is not sorted. Prior to entering this part of the code we need to link two preexising lists together. The directions do not say to sort the two list once they are put together.

Any advice would be helpful.

Thanks

r = first;
    while ( r != nil )
    {
        target = (*r).info;
 
        q = r;
        p = (*q).next;
 
        while ( ((*p).next != nil) )
        {
 
            if ( target == (*p).info )
            {
                (*q).next = (*p).next;
            }
            else
            {
                q = p;
                p = (*p).next;
            }//end if
        }//end while
 
        r = (*r).next;
    }
 

That while condition at line #9 is not correct, i.e. the last node of the list should
be considered to be a duplicate to be removed; make it:

while (p != nil)
 

I realize that 'nil' is part of the pseudo code, make that 'NULL' in your actual code.
You can alse write '(*p).next' as 'p->next'; it's more concise and takes less of
those darn parentheses ;-)

kind regards,

Jos

[twillie]

That while condition at line #9 is not correct, i.e. the last node of the list should
be considered to be a duplicate to be removed; make it:

while (p != nil)
 

I realize that 'nil' is part of the pseudo code, make that 'NULL' in your actual code.
You can alse write '(*p).next' as 'p->next'; it's more concise and takes less of
those darn parentheses ;-)

kind regards,

Jos

Thanks for the advice Jos. nil is actually declared in my program. I agree that it is a little funny, but that is the way the prof wants it. I am still having trouble though. Just prior to this section of code is where I merge the two lists together. If I skip this code above and print out my list I get one long list (both put together) the way I would expect. When I run this code inbetween I only get the values from the second list and then the code stops and wont allow me to 'press any key to continue.' I am really lost because I would expect the code above to work as expected. I think it might have something to do with my pointers, but I am not sure.

Thanks

[JosAH]

When I run this code inbetween I only get the values from the second list and then the code stops and wont allow me to 'press any key to continue.' I am really lost because I would expect the code above to work as expected. I think it might have something to do with my pointers, but I am not sure.

Thanks

Well, you have to show us a bit of relevant code then; we're not psychic ;-)

kind regards,

Jos

[twillie]

Well, you have to show us a bit of relevant code then; we're not psychic ;-)

kind regards,

Jos

I actually figured out what it was. When the two nodes match it makes the update to remove it but never moves the p and q pointers so it gets stuck in a loop. I needed to add the code in the false part of the if to the bottom of the code in the true part.

Thanks for the help!!