自定义链表合并时malloc内存错误排查与功能修复求助

核心错误原因 #

1. 浅拷贝导致重复释放内存
   List类未定义自定义拷贝构造函数和赋值运算符，当vecOfLists.push_back(list)时，会调用默认拷贝构造，仅复制head指针。局部list对象销毁时调用clear()释放所有节点，此时vector中存储的List对象的head指向已释放的内存，后续操作（如merge、析构）再次delete这些指针，触发pointer being freed was not allocated错误。

2. mergeAll函数中的节点所有权冲突

• merge函数是原地合并，会修改传入的链表节点指针。mergeAll中调用vecOfLists.at(i).clear()时，该链表的节点已经被合并到answer中，clear操作会释放这些节点，导致answer中的指针变成野指针。
• 初始的vecOfLists[0].head被赋值给answer，当vector销毁时，vecOfLists[0]的析构函数会调用clear()释放该链表节点，导致最终结果链表的节点被提前释放。

修复步骤 #

1. 禁用List类的拷贝语义，添加移动语义 #

因为链表的所有权应该唯一，禁止拷贝，支持移动：

struct List
{
    List(Node* node) : head(node){}
    List() : head(nullptr){}
    ~List();
    // 禁用拷贝构造和赋值
    List(const List&) = delete;
    List& operator=(const List&) = delete;
    // 添加移动构造和赋值
    List(List&& other) noexcept : head(other.head) {
        other.head = nullptr; // 转移所有权，原对象不再持有节点
    }
    List& operator=(List&& other) noexcept {
        if (this != &other) {
            clear();
            head = other.head;
            other.head = nullptr;
        }
        return *this;
    }
    void clear();
    void push_back(int key);
    void print();
    Node* head;
};

2. 修改mergeAll函数，转移节点所有权 #

合并时将原List的head置空，避免原List析构时释放节点：

Node* mergeAll(std::vector<List>& vecOfLists)
{
    if (vecOfLists.empty()) return nullptr;
    Node* answer = vecOfLists[0].head;
    vecOfLists[0].head = nullptr; // 转移所有权，原List不再持有节点
    for (int i = 1; i < vecOfLists.size(); ++i)
    {
        Node* currentHead = vecOfLists[i].head;
        vecOfLists[i].head = nullptr; // 转移所有权
        answer = merge(answer, currentHead);
        // 不再调用clear()，因为已经转移了所有权
    }
    return answer;
}

3. 主函数中使用移动语义添加List到vector #

将vecOfLists.push_back(list)改为vecOfLists.push_back(std::move(list))，避免拷贝：

int main()
{
    int k = 0;
    std::cin >> k;
    std::vector<List> vecOfLists;
    vecOfLists.reserve(k); // 预分配空间，避免扩容时的移动
    for (int i = 0; i < k; ++i)
    {
         std::string s;
         std::cin >> s;

         std::vector<int> nums;
         getNums(s, nums);
         List list;
         makeList(list, nums);

         vecOfLists.push_back(std::move(list)); // 移动而非拷贝
    }
    List result(mergeAll(vecOfLists));
    result.print();
    std::cout << std::endl; // 输出换行，符合示例格式
}

4. 补充Node类的默认构造函数（可选） #

原Node类的默认构造函数未初始化next指针，可能导致未定义行为，修改为：

struct Node
{
    int val;
    Node* next;
    Node() : val(0), next(nullptr){} // 初始化next
    Node(int x) : val(x), next(nullptr){}
};

修改后完整代码 #

#include <iostream>
#include <vector>
#include <string>
#include <utility> // 用于std::move

struct Node
{
    int val;
    Node* next;
    Node() : val(0), next(nullptr){}
    Node(int x) : val(x), next(nullptr){}
};

struct List
{
    List(Node* node) : head(node){}
    List() : head(nullptr){}
    ~List();
    // 禁用拷贝
    List(const List&) = delete;
    List& operator=(const List&) = delete;
    // 移动构造
    List(List&& other) noexcept : head(other.head) {
        other.head = nullptr;
    }
    // 移动赋值
    List& operator=(List&& other) noexcept {
        if (this != &other) {
            clear();
            head = other.head;
            other.head = nullptr;
        }
        return *this;
    }
    void clear();
    void push_back(int key);
    void print();
    Node* head;
};

void List::push_back(int val)
{
    Node* newNode = new Node(val);
    Node* cur = head;
    if (head != nullptr)
    {
        while(cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newNode;
    }
    else
    {
        head = newNode;
    }
}

void List::print()
{
    Node* cur = head;
    while(cur != nullptr)
    {
        std::cout << cur->val;
        if (cur->next != nullptr)
        {
            std::cout << "--->";
        }
        cur = cur->next;
    }
}

void List::clear()
{
    Node* cur = head;
    while (cur != nullptr)
    {
        Node* a = cur;
        cur = cur->next;
        delete a;
    }
    head = nullptr; // 置空，避免野指针
}

List::~List()
{
    clear();
}

Node* merge(Node* nodeFirst, Node* nodeSecond)
{
    if (!nodeFirst)
    {
        return nodeSecond;
    }

    if (!nodeSecond)
    {
        return nodeFirst;
    }

    if (nodeFirst->val <= nodeSecond->val)
    {
        nodeFirst->next = merge(nodeFirst->next, nodeSecond);
        return nodeFirst;
    }
    else
    {
        nodeSecond->next = merge(nodeSecond->next, nodeFirst);
        return nodeSecond;
    }
}

Node* mergeAll(std::vector<List>& vecOfLists)
{
    if (vecOfLists.empty()) return nullptr;
    Node* answer = vecOfLists[0].head;
    vecOfLists[0].head = nullptr;
    for (int i = 1; i < vecOfLists.size(); ++i)
    {
        Node* currentHead = vecOfLists[i].head;
        vecOfLists[i].head = nullptr;
        answer = merge(answer, currentHead);
    }
    return answer;
}

std::vector<int> getNums(const std::string& s, std::vector<int>& numbers)
{
    size_t num_start = 0, num_end = 0;
    const std::string arrow = "--->";
    while (num_end < s.size())
    {
        num_end = s.find(arrow, num_start);
        if (num_end == std::string::npos)
        {
            num_end = s.size();
        }
        numbers.push_back(std::stoi(s.substr(num_start, num_end - num_start)));
        num_start = num_end + arrow.size();
    }
    return numbers;
}

List& makeList(List& list, const std::vector<int>& nums)
{
    for (const int& x : nums)
    {
        list.push_back(x);
    }
    return list;
}

int main()
{
    int k = 0;
    std::cin >> k;
    std::vector<List> vecOfLists;
    vecOfLists.reserve(k);
    for (int i = 0; i < k; ++i)
    {
         std::string s;
         std::cin >> s;

         std::vector<int> nums;
         getNums(s, nums);
         List list;
         makeList(list, nums);

         vecOfLists.push_back(std::move(list));
    }
    List result(mergeAll(vecOfLists));
    result.print();
    std::cout << std::endl;
}

验证 #

输入示例中的内容，程序会输出正确的合并结果，且无内存错误。

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