需要在C++中实现单链表的归并排序（内存泄漏问题）

Question

我正在做一项作业，以在 C++ 中实现单链表的合并排序。合并函数需要就地合并两个排序列表而不创建新节点。 mergesort 函数应该创建一个新的排序列表而不修改输入列表。我的实现通过了所有测试用例，但存在 Valgrind 检测到的内存泄漏问题。这是相关代码：

#include <utility> // This include is needed for std::declval

/* node
   The node type for our linked list.
*/
struct node {
    int value;
    node* next;

    node(int val) : value(val), next(nullptr) {}
};

/* merge
   Merge the lists given by `left` and `right`, returning the head of the merged
   list (the returned node should either be the head of `left` or the head of
   `right`). The two input lists will always be sorted in ascending order.

   Must run in O(m+n) time where `m` is the length of `left` and `n` is the
   length of `right`.

   Must use O(1) space (i.e., this is an in-place operation); no new nodes 
   may be created.

   NOTE: This function should modify the `next` pointers in the nodes, but NOT
   modify the `value`s. That is, it merges the lists by updating their list
   structure, not by moving values from one list to another.
*/
node* merge(node* left, node* right) {
    if (!left) return right;
    if (!right) return left;

    node* mergedHead = nullptr;
    if (left->value <= right->value) {
        mergedHead = left;
        left = left->next;
    } else {
        mergedHead = right;
        right = right->next;
    }

    node* mergedTail = mergedHead;
    while (left && right) {
        if (left->value <= right->value) {
            mergedTail->next = left;
            left = left->next;
        } else {
            mergedTail->next = right;
            right = right->next;
        }
        mergedTail = mergedTail->next;
    }

    if (left) {
        mergedTail->next = left;
    } else {
        mergedTail->next = right;
    }

    return mergedHead;
}

/* mergesort(input, length)
   Recursively Mergesort the `input` list (whose length is given by `length`),
   returning a new sorted list. 

   Must run in O(n log n) time, where n = `length`.

   Must use O(n) space (returned list is created new). 

   NOTE: The `input` list must not be modified in any way.
*/
node* mergesort(node* input, int length) {
    if (length <= 1) {
        return new node(input->value);
    }

    int mid = length / 2;
    node* left = input;
    node* right = input;
    node* prev = nullptr;

    for (int i = 0; i < mid; ++i) {
        prev = right;
        right = right->next;
    }

    prev->next = nullptr;

    node* sortedLeft = mergesort(left, mid);
    node* sortedRight = mergesort(right, length - mid);

    return merge(sortedLeft, sortedRight);
}

/* mergesort(input)
   Mergesort the list whose head is `input`, returning a new sorted list. This
   function should compute the length of the list, and then pass `input` and
   the length to the two-parameter recursive `mergesort` overload, below.

   Must run in O(n log n) time (but that's because `mergesort(node*,int)`, below
   runs in O(n log n)).

   Must use O(n) space (i.e., the returned list is created new).
*/
node* mergesort(node* input) {
    if (!input) return nullptr;

    int length = 0;
    node* temp = input;
    while (temp) {
        ++length;
        temp = temp->next;
    }

    return mergesort(input, length);
}

Valgrind 信息 我已经尝试了很多事情，但仍然无法让它完全运行。测试用例工作得很好，但我无法找出我的逻辑中关于泄漏的缺陷，我快疯了！请帮忙

Answer 1

问题出在以下分配上：

prev->next = nullptr;

这会改变输入列表。但作业说：

mergesort

函数应该创建一个新的排序列表而不修改输入列表。

通过递归，此突变最终将隔离输入中的每个节点，以便在完成顶级

mergesort

调用后，

input

指针将仅指向没有后继的节点。因此，调用者无法释放属于输入列表的任何其他节点占用的内存。

解决此问题的务实方法是在返回之前撤消该突变。所以改变这个：

    prev->next = nullptr;

    node* sortedLeft = mergesort(left, mid);
    node* sortedRight = mergesort(right, length - mid);

对此：

    prev->next = nullptr;

    node* sortedLeft = mergesort(left, mid);
    node* sortedRight = mergesort(right, length - mid);

    prev->next = right; // restore!

NB：也应该可以根本不改变输入列表，但是您必须将一些额外信息传递给

merge

函数，例如

left

和

right

分区的大小。然后，不应假设分区以

nullptr

结尾，而应跟踪节点计数以了解分区的结尾位置。