c++ - 删除重复链接列表

Question

void RemoveDuplicates(Slist& l)
{
    if (l.head == NULL) {
        return;
    }
    Node* cur = l.head;
    while (cur != NULL && cur->next != NULL) {
        Node* prev = cur;
        Node* temp = cur->next;
        while (temp != NULL) {
            if (temp->data == cur->data) {
                prev->next = temp->next;
                cur->next = prev->next;
                temp = prev->next;
            }
            else {
                prev = prev->next;
                temp = temp->next;
            }
        }
        cur = cur->next;
    }
}

嗨，我想从链表中删除重复项(0为NULL)

input:  1->2->2->4->2->6->0 
outPut: 1->2->4->6->0

运行程序后的结果是:

1->2->6

我哪里错了？请帮我

Answer 1

这是我为您解决的问题的解决方案:

bool alreadyExist(Node head)
{
    Node cur = head;
    while(cur.next != nullptr)
    {
        if(cur.next->data == head.data) {
            return true;
        }
        cur = *cur.next;
    }

    return false;
}

void RemoveDuplicates(Slist& l)
{
    if (l.head == nullptr) {
        return;
    }

    Node* head = l.head;

    Node* curPtr = l.head->next;
    while(curPtr != nullptr)
    {
        if(alreadyExist(*curPtr) == false)
        {
            head->next = curPtr;
            head->next->prev = head;
            head = head->next;
            curPtr = curPtr->next;
        }
        else
        {
            Node* backup = curPtr;
            curPtr = curPtr->next;

            // delete duplicate elements from the heap,
            // if the nodes were allocated with new, malloc or something else
            // to avoid memory leak. Remove this, if no memory was allocated
            delete backup;
        }
    }
}

重要说明:不允许Node对象的析构函数删除next和prev指针后面的链接对象。

对于您的输入示例，结果为 1->4->2->6->0输出。您想要作为输出的顺序并不完全准确，但是每个数字在输出中仅存在一次。它仅添加重复号码的最后一次时间。
我真的不知道，如果您使用C或C++，但是因为我更喜欢C++，所以在代码中将NULL替换为nullptr。如果对象不在使用malloc或new创建的HEAP上，则可以删除删除。