Sum two Linked Lists

Question

I have a node like this:

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

And I want to sum two link lists using recursion. I am not sure, but I guess it is tail recursion.

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

Here is my code:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0,ListNode *result = nullptr) {
    int n1 = l1 != nullptr ? l1->val : 0;
    int n2 = l2 != nullptr ? l2->val : 0;
    int val = (n1 + n2 + carry) % 10;
    if(result == nullptr){
        result = new ListNode(val);
    }else{
        result->next = new ListNode(val);
        result = result->next;
    }
    result = addTwoNumbers(l1->next != nullptr ? l1->next : nullptr,
                           l2->next != nullptr ? l2->next : nullptr, 
                           (n1 + n2 + carry) - 10,result);
    return result;
}

But I am getting a segmentation fault, even when passing two single-node lists:

ListNode * a = new ListNode(1);
ListNode * b = new ListNode(2);
ListNode * c = addTwoNumbers(a, b); 
std::cout << c->val << "\n";

I cannot see what is wrong, it should work. What am I missing?

Answer 1

There are several issues:

• Your recursion never stops, and this is the cause of the segmentation fault -- at the recursive call you evaluate l1->next, but at a certain point l1 will be a nullpointer, and so you get the exception. The so-called "base case" of the recursion is missing. When both list pointers are null and there is no carry, there should not be a recursive call, but instead a null pointer should be returned
• (n1 + n2 + carry) - 10 is the wrong formula. It should be (n1 + n2 + carry) / 10.
• result = result->next; is wrong, as you will for ever lose the reference to the node you just created. Once you create the head of the new list, that head should not need to change again. As you first add the head values together of the parameters, that sum should also come first in the result, and the reference to that first node is what the function should return.

Also:

• It should not be necessary to pass result as a parameter. Make sure the recursive call returns a consistent result (linked list) for the shorter lists that you pass as argument. Then the "only" thing you have to do is to prepend the current sum as a node to that returned list, and you're done. So the result argument is really not needed.

Here is the corrected code:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
    // base case
    if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
    int n1 = l1 != nullptr ? l1->val : 0;
    int n2 = l2 != nullptr ? l2->val : 0;
    int sum = n1 + n2 + carry;
    return new ListNode(sum % 10, 
        addTwoNumbers(l1 != nullptr ? l1->next : nullptr, 
                      l2 != nullptr ? l2->next : nullptr, sum / 10));
}