Сортировка слиянием для односвязных списков дает правильные результаты, но приводит к утечке памяти

Я работаю над заданием по реализации сортировки слиянием для односвязных списков на C++. Функция merge должна объединить два отсортированных списка на месте без создания новых узлов. Функция mergesort должна создать новый отсортированный список без изменения входного списка.

Моя реализация проходит все тестовые случаи, но имеет проблему с утечкой памяти, обнаруженную Valgrind. Вот соответствующий код с примером, запущенным в main внизу:

#include <cstdio>
#include <iostream>

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

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

/* 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);
}

void printlist(node *head) {
    while (head) {
        std::cout << head->value << " ";
        head = head->next;
    }
    std::cout << "\n";
}

int main(){
    // Example input: 4->1->3->2
    node *input = new node(4, new node(1, new node(3, new node(2))));
    node *sorted = mergesort(input);
    printlist(sorted); // 1 2 3 4
    return 0;
}

Вот что сообщает Валгринд:

Я не смог найти, где у меня происходит утечка памяти. Программа возвращает правильные результаты для тестовых случаев, но я не могу обнаружить ошибку в моей логике в отношении утечки. Что мне не хватает?