Mergesort for singly-linked lists gives correct results but leaks memory

Question

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?

Answer 1

The problem is with the following assignment:

prev->next = nullptr;

This mutates the input list. But the assignment said:

The mergesort function should create a new sorted list without modifying the input list.

Through recursion this mutation will eventually isolate every node in the input, so that after you have completed the top-level mergesort call, the input pointer will just point to a node that has no successor. By consequence, the caller has no way to free the memory that is occupied by any other node that belonged to the input list.

The pragmatic way to solve this issue is to undo that mutation before returning (but see further). So change this:

    prev->next = nullptr;

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

to this:

    prev->next = nullptr;

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

    prev->next = right; // restore!

But as your 2-parameter mergesort function does not depend on checking the end of the given list based on a null pointer, but on the given length only (which is good!), you don't actually need to break the input list at all, and can just omit the use of prev.