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;
}
  • 3
    It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm. – DNK Aug 17 at 18:21
  • @Greg, you might be interested in this question. – Incomputable Aug 18 at 20:18
  • 1
    Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks! – Vogel612 Aug 25 at 16:52
  • Did you mean && ./main, rather than | ./main, for your build+run command? – Toby Speight Aug 27 at 7:21
up vote 7 down vote accepted

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.

  • 1
    Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it? – greg Aug 17 at 19:28
  • 1
    @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it. – einpoklum Aug 18 at 7:28
  • 2
    @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code. – einpoklum Aug 18 at 8:25

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.

  • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here. – greg Aug 17 at 20:26

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

  • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use \n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something? – greg Aug 17 at 19:45
  • 1
    (1) Sorry I forgot to mention \n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC. – yuri Aug 17 at 20:02
  • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10 – greg Aug 17 at 20:28
  • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output? – yuri Aug 17 at 20:34
  • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj – greg Aug 17 at 20:49

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 )

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;
  • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks! – greg Aug 20 at 16:22

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.