删除具有重复相同值的已排序链表中的重复值

Question

我在删除那些重复超过1次的值后遇到了打印排序链表的问题。

代码:

Node* RemoveDuplicates(Node *head)
{
    Node *prev,*cur;
    cur=head;
    while(cur->next!=NULL)
        {
        prev = cur;
        cur = cur->next;
        if(prev->data == cur->data)
            {
            prev->next = cur->next;
            free(cur);
        }
    }
    return head;
}

这将删除不止一次出现的值，但对于不止一次的值，它不起作用，我无法找到原因。

测试用例:

例如:如果INPUT是这样的:

4
6
1 2 2 3 3 4
7
1 1 1 1 1 1 1
5
2 3 3 4 6
1
10

那么输出应该像这样:

1 2 3 4
1
2 3 4 6
10

但是我的输出是:

1 2 3 4
1 1 1 1
2 3 4 6
10

Answer 1

由于cur被释放，在while中无法访问它。你可以这样做:

Node* RemoveDuplicates(Node *head)
{
    if(head==NULL){
        return NULL;
    }
    Node *prev,*cur;
    cur=head;
    while(cur->next!=NULL)
    {
        prev = cur;
        cur = cur->next;
        if(prev->data == cur->data)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev;
        }
    }
    return head;
}

Answer 2

这是一种可能的方法。基本思想是遍历列表，只要存在下一个节点和，数据匹配就从列表中截取下一个节点。我添加了一个DeleteNode()辅助函数，释放一个节点并返回它的旧next指针。此实用程序在其他上下文中很有用。

Node* DeleteNode(Node *node)
{
    Node *ptr = node->next;
    delete node; // This is C++, you might need free() instead
    return ptr;
}
Node* RemoveDuplicates(Node *list)
{
    Node *node = list;
    while (node) {
        while (node->next && (node->data == node->next->data)) {
            node->next = DeleteNode(node->next);
        }
        node = node->next;
    }
    return list;
}

Answer 3

这是你的代码的修改版本，我相信它不会出现问题。我在开始时添加了NULL检查，并修改了算法以正确处理重复项:

Node* RemoveDuplicates(Node *head)
{
    if (head == NULL)         // return NULL in case of empty list
        return NULL;
    if (head->next == NULL)   // return the head in case of list with only one element
        return head;
    Node *prev,*cur;
    prev = head;
    cur  = head->next;
    while (cur != NULL)
    {
        if (prev->data != cur->data) {
            prev->next = cur;
            prev = cur;    
            cur = cur->next;
        }
        else {
            Node* temp = cur;
            cur = cur->next;
            free(temp);       // delete a duplicate node
        }
    }
    prev->next = NULL;        // NULL-terminate the modified list
    return head;
}