c - 删除链表中的重复元素

Question

我有一个列表:
1-2-3-3-4-5-6-6-2-7-8-6-9-10-9-NULL//之前
我想做如下:
1-2-3-4-5-6-7-8-9-10-NULL//之后
我写了以下代码:

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);
}

但是输出是:
1-2-3-4-5-6-7-8-6-9-10
请告诉我代码中有什么问题，请更正:)。

Answer 1

尝试以下功能(未经测试)

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;
            }
        }
    }
}

至于你的函数那么连函数的开头都是错的

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

通常 head 可以等于 NULL 在这种情况下，此语句 p=t->next; 会导致未定义的行为。

编辑:如果函数必须是递归的，那么它可以看起来像下面这样

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 );
    }
}