如何在C++链表中检测并移除连续三个相同值的节点？

看起来你在链表操作的逻辑上踩了几个小坑，咱们先拆解一下原代码里的问题，再一步步修正：

原代码的核心问题 #

• 循环内指针重置错误：每次循环都把prev_prev、prev、current重新指向链表头部的三个节点，这会导致你永远只检查前三个节点，没法遍历整个链表。
• 移除节点的逻辑无效：prev_prev = current->next只是修改了局部变量的指向，并没有真正改变链表的指针连接，等于没做移除操作。
• 指针初始化和边界处理缺失：没有考虑链表长度不足3的情况，也没处理头节点可能被移除的场景。

正确的实现思路 #

要跟踪连续重复的节点，我们可以换个思路：不用同时盯着三个指针，而是统计当前连续相同值的节点数量，当数量达到3时，把这一段从链表中“切掉”。另外，建议用**哑节点（dummy node）**来处理头节点被移除的边界情况，这样不用单独写逻辑处理头节点。

修正后的代码 #

#include <iostream>
using namespace std;

// 假设你的Node结构体定义如下
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    
    // 添加节点的辅助方法，用于测试
    void addNode(int val) {
        if (!head) {
            head = new Node(val);
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = new Node(val);
    }
    
    // 打印链表，验证结果
    void printList() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    void Remove_ThreeDuplicates() {
        // 链表长度不足3，直接返回
        if (!head || !head->next || !head->next->next) {
            cout << "0 three pairs of identical node found\n";
            return;
        }

        // 哑节点：避免单独处理头节点被移除的情况
        Node* dummy = new Node(0);
        dummy->next = head;
        Node* prev = dummy; // prev指向当前连续序列的前一个节点
        Node* current = head;
        int count = 1; // 统计连续相同节点的数量，初始为当前节点自身
        int removedCount = 0;

        while (current->next != nullptr) {
            if (current->data == current->next->data) {
                count++;
                current = current->next;
                // 当连续数量达到3时，执行移除操作
                if (count == 3) {
                    // 遍历并删除这3个重复节点
                    while (count > 0 && current != nullptr) {
                        Node* temp = current;
                        current = current->next;
                        delete temp; // 释放内存，避免泄漏
                        count--;
                    }
                    // 重新连接链表：跳过被删除的节点
                    prev->next = current;
                    removedCount++;
                    count = 1; // 重置计数，准备统计下一段序列
                }
            } else {
                // 当前节点和下一个节点不同，移动指针并重置计数
                prev = current;
                current = current->next;
                count = 1;
            }
        }

        // 更新链表头（头节点可能被移除了）
        head = dummy->next;
        delete dummy; // 释放哑节点内存
        cout << removedCount << " three pairs of identical node found\n";
    }
};

// 测试示例
int main() {
    LinkedList list;
    int arr[] = {1, 2, 3, 4, 4, 4, 7, 5};
    for (int num : arr) {
        list.addNode(num);
    }
    cout << "原链表: ";
    list.printList();
    list.Remove_ThreeDuplicates();
    cout << "移除后的链表: ";
    list.printList();
    return 0;
}

代码关键逻辑说明 #

• 哑节点的作用：当链表前三个节点就是重复节点时，我们可以直接通过dummy->next修改头指针，不用单独编写头节点的特殊处理逻辑。
• 连续计数逻辑：用count统计当前连续相同值的节点数，达到3时就遍历删除这一段节点，再通过prev->next = current完成链表的重新连接。
• 内存管理：删除节点时记得释放内存，避免出现内存泄漏问题。

运行这段代码后，你的示例输入1,2,3,4,4,4,7,5会输出移除后的链表1 2 3 7 5，同时显示1 three pairs of identical node found，完全符合预期。

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