Add Two Numbers given in Reverse Order from a Linked List

Question

Updated Question

Problem Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Link to LeetCode. Only code submitted to LeetCode is in AddTwoNumbersHelper and AddTwoNumbers

What I'd like some feedback on

I've written this so that anyone can Compile and Run this program on their machines using the following:

g++ -std=c++11 -Wall -Wextra -Werror Main.cpp -o main | ./main

I'm looking for feedback on this LeetCode question since I've seen many examples in other languages, but not many in C++. Even the example solution in LeetCode is written in Java.

I'm mainly looking for any ways I can optimize my conditional statements and arithmetic, my using statement, and use of pointers.

#include <cstddef>
#include <iostream>
#include <ostream>
#include <stddef.h>
#include <stdlib.h>

using std::cout;
using std::endl;
using std::ostream;
using std::string;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    void printAllNodes()
    {
        ListNode *current = new ListNode(0);
        current = this;
        string nodeString = "LinkedList: ";
        int x = 0;
        while(current != NULL)
        {
            x = current->val;
            // IMPORTANT
            // must compile using C++ 11
            // g++ -std=c++11 -Wall -Wextra -Werror Main.cpp -o main | ./main
            nodeString = nodeString + " -> ( " + std::to_string(x) + " ) ";
            current = current->next;
        }

        cout << nodeString << endl;
    }
};

class Solution
{
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
};
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
{
    ListNode *node = new ListNode(0);
    ListNode *currentNode = new ListNode(0);
    currentNode = node;

    ListNode *currentL1 = new ListNode(0);
    ListNode *currentL2 = new ListNode(0);
    currentL1 = l1;
    currentL2 = l2;

    int sum = 0;
    int carry = 0;

    while(currentL1 != NULL || currentL2 != NULL)
    {
        if (currentL1 == NULL)
        {
            sum = currentL2->val + carry;
            carry = 0;
            currentL2 = currentL2->next;
        } else if (currentL2 == NULL)
        {
            sum = currentL1->val + carry;
            carry = 0;
            currentL1 = currentL1->next;
        } else
        {
            sum = currentL1->val + currentL2->val + carry;
            carry = 0;
            currentL1 = currentL1->next;
            currentL2 = currentL2->next;
        }

        if (sum >= 10)
        {
            carry = sum / 10;
            currentNode->val = sum % 10;
            cout << "sum is " << sum << " with carry of " << carry << endl;
        } else
        {
            currentNode->val = sum;
            cout << "sum is " << sum << endl;
        }

        if (currentL1 == NULL && currentL2 == NULL && sum >= 10)
        {
            currentNode->next = new ListNode(0);
            currentNode = currentNode->next;
            currentNode->val = carry;
        } else if (currentL1 != NULL || currentL2 != NULL)
        {
            currentNode->next = new ListNode(0);
            currentNode = currentNode->next;
        }
    }

    return node;
}

/**
 *
 * Proves this
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveBasicCase()
{
    cout << "\n\nBasic case\n";
    Solution s;

    ListNode *l1 = new ListNode(2);
    ListNode *l1SubA = new ListNode(4);
    ListNode *l1SubB = new ListNode(3);
    l1SubA->next = l1SubB;
    l1->next = l1SubA;

    ListNode *l2 = new ListNode(5);
    ListNode *l2SubA = new ListNode(6);
    ListNode *l2SubB = new ListNode(4);
    l2SubA->next = l2SubB;
    l2->next = l2SubA;

    ListNode *n = new ListNode(0);
    n = s.addTwoNumbers(l1, l2);
    n->printAllNodes();
}

/**
 *
 * Proves this
 * Input: (2 -> 4 -> 3) + (5 -> 6)
 * Output: 7 -> 0 -> 4
 * Explanation: 342 + 65 = 407.
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveListSizeNotEqual()
{
    cout << "\n\nUneven List sizes\n";
    Solution s;

    ListNode *l1 = new ListNode(2);
    ListNode *l1SubA = new ListNode(4);
    ListNode *l1SubB = new ListNode(3);
    l1SubA->next = l1SubB;
    l1->next = l1SubA;

    ListNode *l2 = new ListNode(5);
    ListNode *l2SubA = new ListNode(6);
    l2->next = l2SubA;

    ListNode *n = new ListNode(0);
    n = s.addTwoNumbers(l1, l2);
    n->printAllNodes();
}

/**
 *
 * Input: (9) + (1 -> 9 -> 9 -> 9 -> 8 -> 9 -> 9)
 * Output: 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9
 * Explanation: 9 + 9989991 = 9990000
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveDoubleCarry()
{
    cout << "\n\nDouble Carry\n";
    Solution s;

    ListNode *l1 = new ListNode(9);

    ListNode *l2 = new ListNode(1);
    ListNode *l2SubA = new ListNode(9);
    ListNode *l2SubB = new ListNode(9);
    ListNode *l2SubC = new ListNode(9);
    ListNode *l2SubD = new ListNode(8);
    ListNode *l2SubE = new ListNode(9);
    ListNode *l2SubF = new ListNode(9);
    l2SubE->next = l2SubF;
    l2SubD->next = l2SubE;
    l2SubC->next = l2SubD;
    l2SubB->next = l2SubC;
    l2SubA->next = l2SubB;
    l2->next = l2SubA;

    ListNode *n = new ListNode(0);
    n = s.addTwoNumbers(l1, l2);
    n->printAllNodes();
}

int main()
{
    using std::cout;
    using std::endl;

    cout << "Mr Robot is running prgm..." << endl;

    proveBasicCase();
    proveListSizeNotEqual();
    proveDoubleCarry();

    return 0;
}

Answer 1

Don't write your own container classes when there's no need

The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:

using digit_t = uint8_t; // or unsigned char if you like
using num_in_list_t = std::list<digit_t>;

num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);

Mark const where relevant

Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.

Don't implement your own pretty-printer

You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?

Follow best practices for memory management

With modern C++, you should:

• Avoid using new and delete directly
• Avoid using raw pointers which own the pointed-to data

Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.

More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.

Don't rush to optimize

The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.

De-spaghetti-ize your main loop

Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.

Don't be afraid of recursion

It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.

Answer 2

As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.

---

Current algorithm

Until the end of both lists reached:

1. Get a sum, taking into account if one of them is null

2. Assign the sum to current node, raising carry flag through branching

3. ...

And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.

---

Proposed algorithm

Let me show the algorithm I would implement:

Until either end is reached:

1. Take the sum plus the carry

2. If sum is greater than 9, substract 10 and raise the carry flag

3. Advance lists by one, including the output list

When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.

---

Implementation of proposed algorithm

Standard library evangelist might march on with iterator support, but then will be disappointed:

template <typename InputIterator, typename OutputIterator>
auto fill_rest(InputIterator first, InputIterator last, 
                         OutputIterator d_first, bool has_carry) {
    for (; first != last; ++first) {
        auto digit = *first;
        digit += has_carry;
        has_carry = false;
        if (digit > 9) {
            digit -= 10;
            has_carry = true;
        }
        *d_first++ = digit;
    }

    return std::make_tuple(d_first, has_carry);
}

template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
                         InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
                         OutputIterator d_first) {
    bool has_carry = false;
    while (lhs_first != lhs_last && rhs_first != rhs_last) {
        auto sum = *lhs_first + *rhs_first;
        sum += has_carry;
        has_carry = false;
        if (sum > 9) {
            sum -= 10;
            has_carry = true;
        }
        *d_first++ = sum;
        ++lhs_first;
        ++rhs_first;
    }

    //only one of the following will run, the other will exit immediately
    std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
    std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
    if (has_carry) {
        *d_first++ = 1;
    }

    return d_first;
}

Demo on Wandbox.

It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.

---

Integrating custom linked list nodes into proposed algorithm

As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.

---

Recursion

As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:

1. If both elements are null and there is no carry, return

2. Take the sum plus carry, being careful with nulls

3. Raise the carry flag and decrease sum by 10 if it exceeds 9

4. Go to 1, passing next list element of left, right, and output lists, and carry

5. Write the sum into current output list element

This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.

Answer 3

I'm mainly looking for any ways I can optimize my conditional statements and arithmetic, my using statement, and use of pointers.

You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.

What is this?

  using std::ostream;

and this?

  #include <cstddef>
  #include <ostream>
  #include <stddef.h>
  #include <stdlib.h>

Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.
You're also missing <string>.

As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.

On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.

Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using \n as an alternative. Also have a look at the C++ core guideline for endl.

The using statements in main are even more useless than the earlier ones.

As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you

Answer 4

Use std::vector<int> to store the numbers

Your post does contain

you are given two non-empty linked lists representing two non-negative integers.

It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.

If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be

std::vector<int> l1{9};
std::vector<int> l2{1, 9, 9, 9, 8, 9, 9};

instead of

ListNode *l1 = new ListNode(9);

ListNode *l2 = new ListNode(1);
ListNode *l2SubA = new ListNode(9);
ListNode *l2SubB = new ListNode(9);
ListNode *l2SubC = new ListNode(9);
ListNode *l2SubD = new ListNode(8);
ListNode *l2SubE = new ListNode(9);
ListNode *l2SubF = new ListNode(9);
l2SubE->next = l2SubF;
l2SubD->next = l2SubE;
l2SubC->next = l2SubD;
l2SubB->next = l2SubC;
l2SubA->next = l2SubB;
l2->next = l2SubA;

Get rid of the class Solution.

I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function

std::vector<int> addTwoNumbers(std::vector<int> const& l1,
                               std::vector<int> const& l2);

Use recursive function to add the numbers

Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.

Here's how the two look in my implementation.

void addTwoNumbers(std::vector<int>::const_iterator iter1,
                   std::vector<int>::const_iterator end1,
                   std::vector<int>::const_iterator iter2,
                   std::vector<int>::const_iterator end2,
                   int carry,
                   std::vector<int>& result)
{
    // Check for terminating condition.
    if ( iter1 == end1 && iter2 == end2 && carry == 0 )
    {
        return;
    }

    int sum = carry;
    if ( iter1 != end1 )
    {
        sum += *iter1;
    }
    if ( iter2 != end2 )
    {
        sum += *iter2;
    }

    carry = sum/10;
    sum = sum%10;

    result.push_back(sum);

    if ( iter1 != end1 )
    {
        ++iter1;
    }

    if ( iter2 != end2 )
    {
        ++iter2;
    }

    // Recurse
    addTwoNumbers(iter1, end1, iter2, end2, carry, result);
}

std::vector<int> addTwoNumbers(std::vector<int> const& l1,
                               std::vector<int> const& l2)
{
    std::vector<int> result;
    addTwoNumbers(l1.begin(), l1.end(),
                  l2.begin(), l2.end(),
                  0,
                  result);

    return result;
}

Print the input and output together

It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be

printNumber("First number", l1);
printNumber("Second number", l2);
printNumber("Result", result);

---

Here's a complete listing of my updated version of your program.

#include <iostream>
#include <vector>
#include <string>

void printNumber(std::vector<int>::const_reverse_iterator iter,
                 std::vector<int>::const_reverse_iterator end)
{
    if ( iter == end )
    {
        return;
    }
    std::cout << *iter;
    printNumber(++iter, end);
}

void printNumber(std::string const& label,
                 std::vector<int> const& num)
{
    std::cout << label << ": ( ";
    printNumber(num.rbegin(), num.rend());
    std::cout << " )\n";
}

void addTwoNumbers(std::vector<int>::const_iterator iter1,
                   std::vector<int>::const_iterator end1,
                   std::vector<int>::const_iterator iter2,
                   std::vector<int>::const_iterator end2,
                   int carry,
                   std::vector<int>& result)
{
    // Check for terminating condition.
    if ( iter1 == end1 && iter2 == end2 && carry == 0 )
    {
        return;
    }

    int sum = carry;
    if ( iter1 != end1 )
    {
        sum += *iter1;
    }
    if ( iter2 != end2 )
    {
        sum += *iter2;
    }

    carry = sum/10;
    sum = sum%10;

    result.push_back(sum);

    if ( iter1 != end1 )
    {
        ++iter1;
    }

    if ( iter2 != end2 )
    {
        ++iter2;
    }

    // Recurse
    addTwoNumbers(iter1, end1, iter2, end2, carry, result);
}

std::vector<int> addTwoNumbers(std::vector<int> const& l1,
                               std::vector<int> const& l2)
{
    std::vector<int> result;
    addTwoNumbers(l1.begin(), l1.end(),
                  l2.begin(), l2.end(),
                  0,
                  result);

    return result;
}


/**
 *
 * Proves this
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveBasicCase()
{
    std::cout << "\n\nBasic case\n";

    std::vector<int> l1{2, 4, 3};
    std::vector<int> l2{5, 6, 4};

    auto result = addTwoNumbers(l1, l2);

    printNumber("First number", l1);
    printNumber("Second number", l2);
    printNumber("Result", result);
}

/**
 *
 * Proves this
 * Input: (2 -> 4 -> 3) + (5 -> 6)
 * Output: 7 -> 0 -> 4
 * Explanation: 342 + 65 = 407.
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveListSizeNotEqual()
{
    std::cout << "\n\nUneven List sizes\n";

    std::vector<int> l1{2, 4, 3};
    std::vector<int> l2{5, 6};

    auto result = addTwoNumbers(l1, l2);

    printNumber("First number", l1);
    printNumber("Second number", l2);
    printNumber("Result", result);
}

/**
 *
 * Input: (9) + (1 -> 9 -> 9 -> 9 -> 8 -> 9 -> 9)
 * Output: 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9
 * Explanation: 9 + 9989991 = 9990000
 *
 * NOTE
 * non-empty linked lists representing two non-negative integers
 *
 */
void proveDoubleCarry()
{
    std::cout << "\n\nDouble Carry\n";

    std::vector<int> l1{9};
    std::vector<int> l2{1, 9, 9, 9, 8, 9, 9};

    auto result = addTwoNumbers(l1, l2);

    printNumber("First number", l1);
    printNumber("Second number", l2);
    printNumber("Result", result);
}

int main()
{
    std::cout << "Mr Robot is running prgm..." << std::endl;

    proveBasicCase();
    proveListSizeNotEqual();
    proveDoubleCarry();

    return 0;
}

and its output

Mr Robot is running prgm...


Basic case
First number: ( 342 )
Second number: ( 465 )
Result: ( 807 )


Uneven List sizes
First number: ( 342 )
Second number: ( 65 )
Result: ( 407 )


Double Carry
First number: ( 9 )
Second number: ( 9989991 )
Result: ( 9990000 )

Answer 5

Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:

    ListNode *node = new ListNode(0);            // <-- the only used
    ListNode *currentNode = new ListNode(0);
    currentNode = node;

    ListNode *currentL1 = new ListNode(0);
    ListNode *currentL2 = new ListNode(0);
    currentL1 = l1;
    currentL2 = l2;

all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them. Do appropriate initializataion instead:

    ListNode *node = new ListNode(0);
    ListNode *currentNode = node;

    ListNode *currentL1 = l1;
    ListNode *currentL2 = l2;