C++链表删除重复元素问题（结构体与指针实现）

没问题，咱们来搞定这个用结构体指针实现的链表去重任务。先把你给出的基础代码整理清楚，再补全del_dup()函数的缺失部分，同时给你讲清楚每一步的思路～

基础结构体与全局变量 #

你定义的链表节点结构体和全局变量如下：

struct node {
    int key;
    node *next;
}*start = NULL;
int SIZE = 0; // 添加元素时SIZE会自增

补全删除重复元素的函数 #

先把你给出的未完成函数放出来，再基于两种常见的去重需求补全实现：

需求1：保留每个元素的第一个实例，删除后续重复项 #

这是最常见的去重逻辑，比如链表1->2->2->3->1处理后变成1->2->3。完整函数实现如下：

void del_dup() {
    // 边界情况：空链表或只有一个节点，直接返回
    if (!start || SIZE == 1) {
        return;
    }

    // 外层循环：逐个选取基准节点
    node *current = start;
    while (current != nullptr) {
        node *prev = current;
        node *runner = current->next;

        // 内层循环：检查基准节点之后的所有节点是否重复
        while (runner != nullptr) {
            if (runner->key == current->key) {
                // 找到重复节点，删除并调整指针
                prev->next = runner->next;
                delete runner; // 释放内存，避免泄漏
                runner = prev->next;
                SIZE--; // 同步更新全局节点计数
            } else {
                // 无重复，移动指针继续遍历
                prev = runner;
                runner = runner->next;
            }
        }
        // 基准节点移动到下一个
        current = current->next;
    }
}

实现思路

• 采用双重遍历：外层循环固定一个基准节点，内层循环遍历后续所有节点对比值。
• 遇到重复节点时，通过前驱节点的next指针跳过重复项，同时释放重复节点的内存，并更新SIZE保证计数准确。
• 提前处理空链表、单节点的边界情况，避免空指针访问错误。

需求2：彻底删除所有出现过多次的元素 #

如果你的需求是只要元素重复出现过，就把所有实例都删掉（比如链表1->2->2->3->1处理后变成3），可以用下面的实现：

void del_all_dup() {
    if (!start || SIZE == 1) {
        return;
    }

    // 用dummy节点处理头节点可能被删除的特殊情况
    node *dummy = new node();
    dummy->next = start;
    node *prev = dummy;
    node *current = start;

    while (current != nullptr) {
        bool has_dup = false;
        // 先删除当前节点后续所有重复项
        while (current->next != nullptr && current->key == current->next->key) {
            has_dup = true;
            node *temp = current->next;
            current->next = temp->next;
            delete temp;
            SIZE--;
        }

        if (has_dup) {
            // 当前节点本身也是重复项，删除它
            prev->next = current->next;
            delete current;
            current = prev->next;
            SIZE--;
        } else {
            // 无重复，移动指针继续遍历
            prev = current;
            current = current->next;
        }
    }

    // 更新头节点并释放dummy节点内存
    start = dummy->next;
    delete dummy;
}

实现思路

• 引入dummy节点：避免头节点因为是重复元素而需要单独处理的麻烦。
• 先标记当前节点是否存在重复，若存在则先删除所有后续重复项，再删除当前节点本身。
• 最后同步更新头节点，并释放dummy节点的内存，避免内存泄漏。

注意事项 #

• 每次删除节点后必须更新SIZE，保证这个全局变量和实际链表节点数一致。
• 务必用delete释放被删除节点的内存，避免内存泄漏问题。
• 如果你的链表是有序链表，可以用更高效的单遍历方式（时间复杂度O(n)），不需要双重循环；但如果是无序链表，双重遍历是最直接的实现方式。

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