I’m working on an assignment to implement mergesort for singly-linked lists in C++. The merge function needs to merge two sorted lists in-place without creating new nodes. The mergesort function should create a new sorted list without modifying the input list.

My implementation passes all test cases but has a memory leak issue as detected by Valgrind. Here’s the relevant code, with an example run in main at the bottom:

#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;
}

This is what Valgrind reports:

I haven’t been able to find where I’m leaking memory. The program returns the correct results for the test cases, but I can’t figure out the flaw in my logic in regards to the leakage. What am I missing?