从链表中删除重复项，错误检查

Question

我需要从给定的链接列表中删除所有重复项，但我不确定我的函数是否安全并且可以工作。目前它适用于基本测试。

#include <vector>
#include <algorithm>

struct Node{
    Node* next{};
    int value{};
};

Node* deleteDuplicates(Node* first){
    if(first==nullptr){
        return nullptr;
    }
    std::vector<int> uniqueValues;
    uniqueValues.push_back(first->value);
    Node* curr=first->next;
    Node* prev=first;
    while(curr!=nullptr){
        if(std::find(uniqueValues.begin(),uniqueValues.end(),curr->value)!=uniqueValues.end()){
            prev->next=curr->next;
            delete curr;
            curr=prev->next;
            continue;
        }
        uniqueValues.push_back(curr->value);
        prev=curr;
        curr=curr->next;
    }
    return first;
}

Answer 1

它工作正常。我们可以通过将唯一值放入

set

而不是

vector

来提高时间复杂度。

set

中的查找具有更好的时间复杂度。

那么：

Node* deleteDuplicates(Node* first) {
    if (!first) {
        return nullptr;
    }
    std::set<int> uniqueValues;
    uniqueValues.insert(first->value);
    Node* curr = first->next;
    Node* prev = first;
    while (curr) {
        // C++20: you can use the contains method instead:
        if (uniqueValues.find(curr->value) != uniqueValues.end()) {
            prev->next = curr->next;
            delete curr;
            curr = prev->next;
            continue;
        }
        uniqueValues.insert(curr->value);
        prev = curr;
        curr = curr->next;
    }
    return first;
}