删除链表中的重复元素

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 //After
我写了以下代码：

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

你应该有一个嵌套的 while:

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

Answer 2

尝试以下功能（未经测试）

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

删除链表中的重复元素

delete duplicate elements in linked list

c

pointers

duplicates

singly-linked-list