C++自定义链表使用raw指针实现去重功能输出异常如何修复?
现有代码问题排查
- 变量未初始化:
numDeletions声明后没有赋初始值,野值会导致后续恢复顺序的循环次数完全随机,是结果偶发正确的核心原因之一 - 指针失效:外层循环的
outerElem仅初始赋值为头节点,后续遍历过程中频繁调用push_back、pop_front修改链表结构,outerElem会指向已被释放的节点,取值cmp完全错误 - 循环边界错误:内层循环的边界依赖动态变化的
size_,当触发删除逻辑仅执行pop_front时,size_会减小,导致遍历范围不符合预期 - 内存访问违规:遍历过程中同时修改链表节点结构,
innerElem会频繁访问已出队被释放的节点,触发未定义行为
合规去重实现方案
不需要借助额外容器,直接通过双向链表的指针操作实现即可,逻辑清晰无冗余,时间复杂度为O(n²),符合自定义链表的实现约束,会保留第一个出现的元素、删除后续所有重复项,完全匹配输入输出示例要求:
void unique(){ if (this->size_ <= 0){ throw std::domain_error("unique() : must be 1 or more elements"); } if (this->size_ == 1) { return; } // 外层遍历:固定当前待检查的基准节点 Node* curr = this->head_; while (curr != nullptr && curr->next != nullptr) { // 内层遍历:从基准节点的下一个节点开始找重复值 Node* traverse = curr->next; while (traverse != nullptr) { if (traverse->data == curr->data) { // 找到重复节点,先保存下一个节点的指针 Node* del_node = traverse; traverse = traverse->next; // 调整链表指针删除重复节点 del_node->prev->next = del_node->next; if (del_node->next != nullptr) { del_node->next->prev = del_node->prev; } else { // 删除的是尾节点,更新tail_ this->tail_ = del_node->prev; } delete del_node; this->size_--; } else { // 无重复,继续往后遍历 traverse = traverse->next; } } // 基准节点后移 curr = curr->next; } }
内容的提问来源于stack exchange,提问作者VinDiesel_
相关产品推荐
相关产品推荐

