“Add two numbers given in reverse order from a linked list”

Question

Original 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.

I've written this so that anyone can compile and run this program on their machines with:

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

I'm looking for feedback on this LeetCode question after modifying the code from feedback in my Original Question. Here is what has changed:

• The solution now uses recursion

• The main logic is not spaghetti code anymore

• Dealt with dangling pointers

What I'd like some feedback on

I'm still a bit unclear on the best practice for how to handle the namespace and usings, as well as how to find the time and space complexity for this.

#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 Node
{
    int val;
    Node *next;
    Node(int val) : val(val), next(NULL) {}

    void PrintAllNodes()
    {
        Node *current = new Node(0);
        current = this;
        std::string nodeString = "LinkedList: ";
        int val = 0;
        while(current != NULL)
        {
            val = current->val;
            nodeString = nodeString + " -> ( " + std::to_string(val) + " ) ";
            current = current->next;
        }

        std::cout << nodeString << '\n';
    }

    void Append(int i)
    {
        if (this->next == NULL)
        {
            Node *n = new Node(i);
            this->next = n;
        }
        else { this->next->Append(i); }
    }
};

class Solution
{
    public:
        Node *AddTwoNumbers(Node *l1, Node *l2);
    private:
        Node *AddTwoNumbersHelper(Node *l1, Node *l2, int sum, int carry, Node *current, Node *head);
};
Node *Solution::AddTwoNumbers(Node *l1, Node *l2)
{
    Node *head = new Node(0);
    Node *current = head;

    int sum = 0;
    int carry = 0;

    return AddTwoNumbersHelper(l1, l2, sum, carry, current, head);
}

Node *Solution::AddTwoNumbersHelper(Node *l1, Node *l2, int sum, int carry, Node *current, Node *head)
{
    if (l1 == NULL && l2 == NULL)
    {
        head = head->next;
        return head;
    }

    sum = 0;
    if (l1 == NULL) { sum = l2->val + carry; }
    else if (l2 == NULL) { sum = l1->val + carry; }
    else if (l1 != NULL && l2 != NULL) { sum = l1->val + l2->val + carry; }

    if (sum >= 10)
    {
        carry = sum / 10;
        sum -= 10;
    }
    else { carry = 0; }

    Node *next = new Node(sum);
    current->next = next;

    if (l1 == NULL) { return AddTwoNumbersHelper(l1, l2->next, sum, carry, current->next, head); }
    else if (l2 == NULL) { return AddTwoNumbersHelper(l1->next, l2, sum, carry, current->next, head); }
    else if (l1 != NULL && l2 != NULL) { return AddTwoNumbersHelper(l1->next, l2->next, sum, carry, current->next, head); }

    return head;
}

/**
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 */
void ProveBasicCase()
{
    cout << "\n\nBasic case\n";
    Solution s;

    Node *l1 = new Node(2);
    l1->Append(4);
    l1->Append(3);

    Node *l2 = new Node(5);
    l2->Append(6);
    l2->Append(4);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

/**
 * Input: (2 -> 4 -> 3) + (5 -> 6)
 * Output: 7 -> 0 -> 4
 * Explanation: 342 + 65 = 407.
 */
void ProveUnEqualListSize()
{
    cout << "\n\nUneven List sizes\n";
    Solution s;

    Node *l1 = new Node(2);
    l1->Append(4);
    l1->Append(3);

    Node *l2 = new Node(5);
    l2->Append(6);

    Node *n = new Node(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
 */
void ProveDoubleCarry()
{
    cout << "\n\nDouble Carry\n";
    Solution s;

    Node *l1 = new Node(9);

    Node *l2 = new Node(1);
    l2->Append(9);
    l2->Append(9);
    l2->Append(9);
    l2->Append(8);
    l2->Append(9);
    l2->Append(9);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

int main()
{
    cout << "mr.robot prgm running...\n";

    ProveBasicCase();
    ProveUnEqualListSize();
    ProveDoubleCarry();

    return 0;
}

Answer 1

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

You've got some unnecessary includes here. <cstddef> and <stddef.h> are the C++ and C versions of the same content. You should be using the C++ version (<cstddef>) and not the C version. Unless you are targeting C++03 and earlier or require the std::ostream definitions, you don't need to include <ostream> with <iostream>. With C++11, <iostream> is guaranteed to include <istream>/<ostream> as needed for the global objects std::cout and friends. The only other use for <ostream> is std::endl, which you don't use anyway.

---

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

Neither endl or ostream appear beyond these using-declarations. string is used once and is qualified with std::. You should remove those.

Avoid using declarations (using std::cout) and directives (using namespace std;) at the global scope of header files. All subsequent lookups in translation units that include your header will pollute the global namespace with those symbols, leading to compilation errors due to ambiguous usage, maintenance, and reuse problems. Namespaces help separate identifiers and make interfaces explicit. If you want to opt into argument dependent lookup, use these declarations/directives in the smallest scope possible.

---

struct Node {
    int val;
    Node *next;
    Node(int val) : val(val), next(NULL) {}

    void PrintAllNodes() {/*...*/}
    void Append(int i) {/*...*/}
};

Rather than extending through modification a class you do not own (ListNode from LeetCode), you can extend through composition. Write an iterator adaptor to traverse the provided forward list that inspects elements. Write another iterator adaptor to insert after your current node. With these two iterators, you can utilize these C structures with the C++ standard library.

In your own code, use nullptr instead of NULL. nullptr is a well-specified and very restrictive type, which isn't vulnerable to the type deduction errors that NULL is.

---

        Node *current = new Node(0);

Avoid new/delete. You create a new node, but you do not delete it. Who is responsible for cleaning up after this node?

        Node *current = new Node(0);
        current = this;
        /* ... */
        while(current != NULL) {
            val = current->val;
            nodeString = nodeString + " -> ( " + std::to_string(val) + " ) ";
            current = current->next;
        }

Don't introduce a variable until you need it and keep the scope of variables as narrow as possible. When there is an obvious loop variable, prefer a for-statement.

For long lists, you are likely to have multiple reallocations of nodeString. Since you are just constructing the stream to be streamed out, consider bypassing the string construction and just stream the pieces directly.

        std::cout << "LinkedList: -> ( " << val << " ) ";
        for (Node* current = next; current != nullptr; next = next->current) {
            std::cout << " -> ( " << current->val << " ) ";
        }
        std::cout << '\n';

---

Node *Solution::AddTwoNumbers(Node *l1, Node *l2) {
    Node *head = new Node(0);

Every time you add two lists together, you leak this head node.

Node *Solution::AddTwoNumbersHelper(Node *l1, Node *l2, int sum, int carry, Node *current, Node *head) {
    if (l1 == NULL && l2 == NULL) {
        head = head->next;
        return head;
    }

Here, head is advanced and returned. Nobody cleans up the head that was incremented from.

What happens if both are lists are the same length and there is a carried 1 after summing both lists?

    int sum = 0;

There is no reason for sum to exist at this point. Declaring sum where you reset it in the helper allows it to be used as scratch space.

    if (sum >= 10) {
        carry = sum / 10;
        sum -= 10;
    }
    else { carry = 0; }

Clang/GCC converts the division to a multiplication, but you can reduce the strength of that operation further if you think about how digits work when added together. Consider the maximum digit (9) and add it with another maximum digit (9). The result (18) will never carry more than one, even if you added a carry from a previous addition (18 + 1 = 19). With that knowledge, we can remove the division and set carry to be whether the digit overflowed.

    carry = sum > 9;
    if (carry) {
        sum -= 10;
    }

carry will either be 1 (overflowed) or 0.

---

void ProveBasicCase() {
    cout << "\n\nBasic case\n";
    Solution s;

    Node *l1 = new Node(2);
    l1->Append(4);
    l1->Append(3);

    Node *l2 = new Node(5);
    l2->Append(6);
    l2->Append(4);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

Ease your cognitive load during tests. Instead of looking through the output and remembering what the output should be, programmatically compare the observed result with an expected result. Pick a testing framework (DocTest, Catch2, GoogleTest, Boost.Test) and start writing actual tests.

#define DOCTEST_IMPLEMENT_WITH_MAIN
#include <doctest.h>

struct NodeList { /* ... */ };

template <typename... Args>
NodeList* make_node_list(Args... args) { /*...*/ }

NodeList* sum_lists(NodeList* list1, NodeList* list2) { /* ... */ }

TEST_CASE("Basic case") {
    auto l1 = make_node_list(2, 4, 3);
    auto l2 = make_node_list(5, 6, 4);

    auto l3 = sum_lists(l1, l2);

    CHECK(l3 != nullptr);
    CHECK(l3->next != nullptr);
    CHECK(l3->next->next != nullptr);
    CHECK(l3->next->next->next == nullptr);

    CHECK(l3->val == 7);
    CHECK(l3->next->val == 0);
    CHECK(l3->next->next->val == 8);
}

---

I'm still a bit unclear on the best practice for how to handle the namespace and usings

Use them when you want to opt into ADL or want to use literals. Keep their uses limited to the narrowest scope required and never in the global scope of a header file (or file included by a header). Read more here.

as well as how to find the time and space complexity for this.

\$\mathcal{O}(m+n)\$ time where \$m\$ and \$n\$ are the lengths of each list. Space will just be the max of \$m\$ and \$n\$. An iterative way to think about it is,

while list1 is not exhausted
    if list2 is exhausted
        sum list1 elements w/carry into result
        when list1 is exhausted, append carry if still carrying
        return result
    sum current element from list1, list2, & carry into result
sum list2 w/carry into result
when list2 is exhausted, append carry if still carrying
return result