"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;
}

• esote: When you compile your program, why do you pipe the output of g++ into ./main? Did you mean to use a semicolon, or a logical operator of some sort?
• yuri: Did you paste the right code? This looks eerily similar to your old version right down to having the same issues.
• Incomputable: @yuri, the if chain is gone, which I think is enough for the time being. Of course we'd like to ask for more.
• esote: @GregDegruy The pipe just takes the output from g++ and tries to put it into your program. You probably meant && or ; instead of |. See: stackoverflow.com/q/9834086/6789498
• Incomputable: @greg, I made some changes to the post, which I hope will improve attractiveness of the question. Please feel free to roll back if I did something wrong. Also don't hesitate to add items to changed list, as it tells reviewers that they successfully delivered knowledge to implement it. Rejected suggestions could use some explanation too.

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 

• greg: Really appreciate the feedback, I have a much deeper understanding of everything from this post now. Implemented most of the changes, working on iterator adaptor next, here github.com/gregdegruy/code/tree/master/leetcode/cpp/….
• greg: any resources you can share that show how to do the following "Rather than extending through modification a class you do not own (ListNode from LeetCode), you can extend through composition"
• Snowhawk: Read up on the "Open/Closed Principle" in SOLID design. While it's meant for object oriented design, the concept is still applicable to functional design.