单链表去重问题求助：C++代码删除函数异常排查

核心问题 #

1. 去重函数的迭代器失效：在removeduplicates中，调用deletenode(compare->data)会删除第一个匹配该值的节点，而非当前的compare节点，逻辑完全错误。而且删除后compare指向的内存已被释放，后续执行compare=compare->next会访问非法内存，触发未定义行为（程序可能崩溃、无输出或产生乱码）。
2. deletenode函数的缺陷：
   • 若链表中不存在目标值，currnode会变为nullptr，后续访问currnode->next会直接崩溃；
   • 计数遍历的方式效率低下，且容易因链表结构变化导致计数错误；
   • 删除尾节点的逻辑依赖计数，一旦计数出错会导致tail指针维护错误。

修复后的完整代码 #

#include<bits/stdc++.h>
using namespace std;

class node{
public:
    int data;
    node *next;
    node(int d) : data(d), next(nullptr) {}
};

class ll
{
private:
    node *head = nullptr;
    node *tail = nullptr;
public:
    void inserthead(int value)
    {
        node *newnode = new node(value);
        if(!head)
        {
            head = newnode;
            tail = newnode;
        }
        else{
            newnode->next = head;
            head = newnode;
        }
    }
    void inserttail(int value)
    {
        node *newnode = new node(value);
        if(!tail)
        {
            head = newnode;
            tail = newnode;
        }
        else{
            tail->next = newnode;
            tail = newnode;
        }
    }
    void print()
    {
        node *temp = head;
        while(temp)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // 修复后的删除函数：删除第一个匹配值的节点，同时维护head和tail
    void deletenode(int value)
    {
        if(!head) return; // 空链表直接返回

        node *curr = head;
        node *prev = nullptr;

        // 找到要删除的节点及其前驱
        while(curr && curr->data != value)
        {
            prev = curr;
            curr = curr->next;
        }

        if(!curr) return; // 未找到目标节点，返回

        // 删除节点
        if(!prev)
        {
            // 删除头节点
            head = head->next;
            if(!head) tail = nullptr; // 删完后链表为空，tail置空
        }
        else
        {
            prev->next = curr->next;
            if(!curr->next) tail = prev; // 删除的是尾节点，更新tail
        }

        delete curr;
    }

    // 修复后的去重函数：直接遍历处理，避免迭代器失效
    void removeduplicates()
    {
        node *curr = head;
        while(curr)
        {
            node *prev = curr;
            node *compare = curr->next;
            while(compare)
            {
                if(compare->data == curr->data)
                {
                    // 保存下一个节点，避免删除后指针失效
                    node *temp = compare->next;
                    // 直接删除当前compare节点
                    prev->next = temp;
                    if(!temp) tail = prev; // 如果删除的是尾节点，更新tail
                    delete compare;
                    compare = temp; // 跳到下一个节点
                }
                else
                {
                    prev = compare;
                    compare = compare->next;
                }
            }
            curr = curr->next;
        }
    }
};

int main()
{
    ll l1;
    l1.inserthead(10);
    l1.inserthead(10);
    l1.inserttail(9);
    l1.inserttail(8);
    l1.inserttail(11);
    l1.removeduplicates();
    l1.print(); // 输出：10 9 8 11
    return 0;
}

关键修复点说明 #

1. deletenode函数：
   • 改用前驱指针+当前指针的方式遍历，避免计数错误；
   • 添加空链表、未找到目标节点的边界判断，防止崩溃；
   • 正确维护head和tail指针，确保链表结构完整。
2. removeduplicates函数：
   • 遍历过程中直接操作节点，删除重复节点时先保存下一个节点的指针，避免迭代器失效；
   • 实时维护prev指针，确保链表的链接关系正确；
   • 删除尾节点时及时更新tail指针，避免后续操作出错。

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