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

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

那么它应该有这样的输出：

但我的输出是：

Answer 1

这是您的代码的改进版本，我相信运行不会有任何问题。我在开头添加了一个 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;
}

Answer 2

这是一种可能的方法。基本思想是遍历列表，只要存在下一个节点和，数据匹配就会从列表中删除下一个节点。我添加了一个 DeleteNode() 辅助函数来释放一个节点和 returns 它是旧的 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

由于 cur 被释放，暂时无法访问它。你可以这样做：

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

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

Deleting duplicate values in a sorted linked list with repeating same values

c++

linked-list

data-structures