Pranav Saxena
Pranav Saxena

Reputation: 13

delete duplicate elements in linked list

I have a list:
1-2-3-3-4-5-6-6-2-7-8-6-9-10-9-NULL //Before
I wnt to make it as following:
1-2-3-4-5-6-7-8-9-10-NULL //After
I have written following code:

void don(struct node *head)
{
struct node *t,*p,*q;
t=head;
p=t->next;//p is to check each node!
q=t;//q is used to take care of previous node!
while(p!=NULL)
{
    if(p->data==t->data)
    {
        while(p->data==t->data)
        {
            p=p->next;
        }
        q->next=p;
        q=q->next;

    }
    else
    {
        p=p->next;
        q=q->next;
    }
}
t=t->next;
if(t!=NULL)
    don(t);
}

But the output is :
1-2-3-4-5-6-7-8-6-9-10
Please tell me what is wrong in the code and please correct it :).

Upvotes: 1

Views: 467

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 311186

Try the following function (without testing)

void don( struct node *head )
{
    for ( struct node *first = head; first != NULL; first = first->next )
    {
        for ( struct node *current = first; current->next != NULL; )
        {
            if ( current->next->data == first->data )
            {
                struct node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }
    }
}

As for your function then even the beginning of the function is wrong

void don(struct node *head)
{
struct node *t,*p,*q;
t=head;
p=t->next;//p is to check each node!
//...

In general head can be equal to NULL In this case this statement p=t->next; results in undefined behaviour.

EDIT: If the function must be recursive then it can look the following way

void don( struct node *head )
{
    if ( head )
    {
        for ( struct node *current = head; current->next != NULL; )
        {
            if ( current->next->data == head->data )
            {
                struct node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }

        don( head->next );
    }
}

Upvotes: 1

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

You should have a nested while:

p= head;
while(p)
{
    q=p->next;
    while(q)
    {
        if (p->data==q->data)
            ...  //remove
        q= q->next;
    }
    p= p->next;
}

Upvotes: 0

Related Questions