C++单链表replace函数问题排查：替换指定值为多个1节点

问题背景 #

我正在实现C++中的SinglyLinkedList类，类维护链表的head、tail指针以及记录节点数的size变量。目标是实现replace(int x)函数：将链表中每个值为x的节点替换为x个值为1的节点。例如原链表为4 -> 5 -> 3 -> 8 -> 5，调用replace(3)后，预期结果为4 -> 5 -> 1 -> 1 -> 1 -> 8 -> 5；若x不存在于链表中，则链表保持不变。

类接口定义：

struct SinglyLinkedList
{
    Node* head, * tail;
    int size;

    SinglyLinkedList() :head(nullptr), tail(nullptr), size(0) {}; // Default constructor
  
    void replace(int X);
};

我的实现代码：

void SinglyLinkedList::replace(int X)
{
    Node dummyHead(0, head);
    Node* curr = head, * prev = &dummyHead;
    while (curr)
    {
        if (curr->value == X)
        {
            Node* nextNode = curr->next;
            for (int i = 0; i < X; i++)
            {
                prev->next = new Node(1);
                size++;
                prev = prev->next;
            }
            if (curr == tail)
            {
                tail = prev;
            }
            prev->next = nextNode;
            curr = nextNode;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummyHead.next;
}

我的实现思路是遍历链表，维护当前节点curr和前驱节点prev，找到值为x的节点时插入x个值为1的新节点；使用哑节点简化头部替换逻辑，同时更新size。但测试中发现函数存在问题，希望排查问题，比如tail的更新逻辑是否有疏漏？

问题排查与修正 #

1. 内存泄漏问题 #

当前代码中，找到值为X的节点后，只是跳过了该节点，但没有释放其内存，会造成内存泄漏。需要在处理完替换逻辑后，调用delete curr释放原节点。

2. size计算错误 #

原逻辑只对新增的x个节点执行了size++，但没有减去被替换掉的那个节点的计数。正确的逻辑应该是：先size--（移除原节点），再新增x个节点时执行x次size++。例如原链表有一个值为3的节点，size为5，替换后size应为5-1+3=7，但原代码会得到5+3=8，与实际节点数不符。

3. tail更新逻辑的验证 #

当前的tail更新逻辑是正确的：当被替换的节点是原链表的tail时，将tail指向最后一个新增的1节点（即prev），这符合预期。除非X=0（但题目场景中X应为正整数，无需额外处理）。

修正后的代码 #

void SinglyLinkedList::replace(int X)
{
    Node dummyHead(0, head);
    Node* curr = head, * prev = &dummyHead;
    while (curr)
    {
        if (curr->value == X)
        {
            Node* nextNode = curr->next;
            // 减去被替换的原节点计数
            size--;
            // 插入X个值为1的节点
            for (int i = 0; i < X; i++)
            {
                prev->next = new Node(1);
                size++;
                prev = prev->next;
            }
            // 更新tail（如果原节点是tail）
            if (curr == tail)
            {
                tail = prev;
            }
            prev->next = nextNode;
            // 释放原节点内存
            delete curr;
            curr = nextNode;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummyHead.next;
}

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