链表去重函数的安全性与正确性验证咨询

我写了一个删除链表中重复节点的函数，已经通过基础测试，但不确定它是否安全、能否稳定运行，代码如下：

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

运行正确性分析 #

• 这个函数的核心逻辑是用vector记录已出现的节点值，遍历链表时，若当前节点值已存在就删除节点并调整指针，否则将值存入vector继续遍历。对于无环单链表，它能正常完成「保留首次出现的节点，删除后续重复节点」的功能，基础测试通过也符合这个表现。
• 注意：如果你的需求是「删除所有出现过重复的节点（某个值出现多次则所有对应节点都删掉）」，那这个函数逻辑不匹配——它只会删掉后续重复项，保留第一个出现的节点。

安全性与潜在问题 #

• 内存安全：函数用delete删除节点，要求所有被删节点都是通过new在堆上分配的。如果节点是栈上创建或用其他内存分配方式（比如内存池），调用delete会触发未定义行为，这是最大风险点。
• 空指针防护：函数开头判断了first为空的情况，遍历过程中对指针的操作也没有空指针访问问题，这部分处理安全。
• 性能隐患：std::find在vector上是线性查找，链表节点较多时时间复杂度会达到O(n²)，运行效率很低。可以换成std::unordered_set存储已出现的值，把查找的平均时间复杂度降到O(1)来优化。
• 环形链表处理：如果输入链表带环，while(curr!=nullptr)会无限循环，函数未处理这种边界情况。
• 线程安全：函数没有线程同步机制，多线程同时操作同一链表会出现数据竞争，仅适用于单线程场景。

总结 #

在**单线程、链表无环、所有节点均为堆分配（new创建）**的前提下，这个函数是安全且能正常运行的，但要确认它的功能是否匹配你的实际需求。如果涉及环形链表、非堆分配节点或多线程场景，需要针对性修改代码。

内容的提问来源于stack exchange，提问作者figipigiel