带头、尾、大小管理的链表替换功能

Question

我正在 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。我使用虚拟头来简化插入逻辑，特别是在处理边缘情况（例如替换列表头）时。插入新节点后，我正确连接列表的其余部分并确保大小相应更新。

由于我正在数据结构和算法课程中完成一项更大的作业（包括测试），因此我已经能够确定问题出在这个函数中。我可以获得帮助来查明问题吗？有什么明显不起作用的事情吗？也许我在所有情况下都没有正确更新尾部？

Answer 1

我相信您的代码不处理原始链表节点的删除。考虑显式删除它们以避免内存泄漏

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;
            }
            delete curr; // free memory of original node
            prev->next = nextNode;
            curr = nextNode;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummyHead.next;
}