删除链表中的重复项

Question

void List::removeDup()
{
    Node *after = NULL;
    Node *dup = NULL;
    curr = head;
    while(curr->next != NULL)
    {
       after = curr->next; //node after current one
       while(after != NULL) 
       {
          if(curr->data == after->data) //if dup found
          {
             dup = after; 
             curr->next = after->next;
             delete dup;
          }
          else
          {
             after = after->next;
          }//if no dup found, advance after node
       }
          curr = curr->next; //advance curr node
    }
}

这段代码使用第一个节点，并与其他节点进行比较以查找重复项。如果找到，它将被删除。我得到的错误是

未分配被释放的

指针。有人知道这是什么意思吗?

如有任何帮助，不胜感激

Answer 1

如果你在linux上尝试运行valgrind看看内存中实际发生了什么

其次，你的代码有问题:当你发现一个重复的，你打破你的链表

节点当前

| | => | | => | |节点=> | | =>复制下| |

如果你发现一个重复的代码，你的代码将当前的下一个点变成重复的下一个点，并将其全部中断

我认为你必须做一个更简单的函数来删除列表中的一个元素，当你发现一个重复的

Answer 2

我创建了这个简单而干净的方法。

这个想法是检查当前节点的数据是否等于下一个节点的数据。

如果答案是肯定的，跳过next one并删除它(释放它)。

如果在给定位置没有重复项，就像往常一样解析链表(else语句)。

Node* RemoveDuplicates(Node *head)
{
    if (head == nullptr) return nullptr;
    Node *curr = head;
    Node *aux;
    while (curr->next != nullptr) {
      if (curr->data == curr->next->data) {
          aux = curr->next->next;
          delete curr->next;
          curr->next = aux;
      }
      else {
          curr = curr->next;
      }  
  }
  return head;
}

Answer 3

我不太了解c++，但我认为这是因为你从来没有分配dup。在c++中删除指针

Answer 4

我几乎在做同样的操作:选择第一个，将其与以下项目进行比较，如果任何以下项目重复，则断开其链接。等等…

这是我的实现:

template<typename T>
void LinkedList<T>::removeDuplicates() {
    Node<T> * current = head;
    while (current) {
        Node<T> * forward_head = current->next;
        Node<T> * forward_tail = current;
        while (forward_head) {
            if (forward_head->data == current->data) {
                // duplicated item found.
                forward_tail->next = forward_head->next;
            }
            else
                forward_tail = forward_tail->next;
            forward_head = forward_head->next;
        }
        current = current->next;
    }
}

期望输出:

移除前:2、2、2、2、3、2、1、3、8、3、2、4、4

删除后:2,3,1,8,4