trjhtr

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.

Example:

Input: (2,4,3) + (5,6,4)

Output: 7,0,8

Explanation: 342 + 465 = 807

I did a coding problem and I am wondering what I could have done better or done differently.

 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
 ListNode *l3 = new ListNode(0);

 if(l1->next!=NULL && l2->next!=NULL)
 
 l3->next = addTwoNumbers(l1->next,l2->next);

 if(l3->next->val>9)
 
 ListNode *temp;
 temp = l3;
 while(temp->next->val>9)
 
 temp->next->next->val+=1;
 temp->next->val-=10;
 l3->val = l1->val+l2->val;
 temp = temp->next;
 
 return l3;
 

 else
 l3->val = l1->val + l2->val;

 if(l3->val>9)
 
 ListNode *tempB;
 tempB = l3;
 while(tempB->val>9)
 
 if(tempB->next != NULL)
 
 tempB->next->val+=1;
 tempB->val-=10;
 tempB = tempB->next;
 
 else 

 ListNode *H = new ListNode(1);
 tempB->next = H;
 tempB->val -= 10;
 tempB = tempB->next;

 
 
 return l3;
 


 return l3;
 

 

 else if(l1->next == NULL && l2->next != NULL)
 
 ListNode *temp = new ListNode(0);
 l3->next = addTwoNumbers(temp,l2->next);
 l3->val = l1->val + l2->val;
 if(l3->val>9)
 
 ListNode *tempB;
 tempB = l3;
 while(tempB->val>9)
 
 if(tempB->next != NULL)
 
 tempB->next->val+=1;
 tempB->val-=10;
 tempB = tempB->next;
 
 else 

 ListNode *H = new ListNode(1);
 tempB->next = H;
 tempB->val -= 10;
 tempB = tempB->next;

 
 
 return l3;
 
 else 
 return l3;
 

 else if(l2->next == NULL && l1->next != NULL)
 
 ListNode *temp = new ListNode(0);
 l3->next = addTwoNumbers(l1->next,temp);
 l3->val = l1->val + l2->val;
 if(l3->val>9)
 
 ListNode *tempB;
 tempB = l3;
 while(tempB->val>9)
 
 if(tempB->next != NULL)
 
 tempB->next->val+=1;
 tempB->val-=10;
 tempB = tempB->next;
 
 else 

 ListNode *H = new ListNode(1);
 tempB->next = H;
 tempB->val -= 10;
 tempB = tempB->next;

 
 
 return l3;
 
 else 
 return l3;
 

 else
 l3->val = l1->val + l2->val;
 if(l3->val>9)
 
 ListNode* l4 = new ListNode(1);
 l3->val -=10;
 l3->next = l4;
 return l3;
 
 else
 return l3;
 

 

Well, your code treats just about everything as a special-case. That not only lacks elegance, it's very verbose, error-prone and inefficient.

1. First, the problem is symmetrical in the two arguments. So, you can swap the arguments without changing anything.


2. You are only reading the passed lists, never modifying them. So, const seems appropriate.


3. If an allocation throws, you simply leak all already-allocated nodes. That's generally inacceptible.


4. Consider writing a proper list-class instead of throwing around loose nodes.


5. Your problem is better solved with iteration than recursion, as C++ does not do GC nor guarantees tail-recursion.

So, let's look at it again, but use iteration. Still, I won't write the list-abstraction, as that would be a major part in itself:

 ListNode* addTwoNumbers(const ListNode* a, const ListNode* b) 
 ListNode dummy(0);
 auto p = &dummy;
 int carry = 0;

 try 
 while (a && b) 
 carry += a->val + b->val;
 p = p->next = new ListNode(carry % 10);
 carry /= 10;
 a = a->next;
 b = b->next;
 

 if(b)
 a = b;
 while (a) 
 carry += a->val;
 p = p->next = new ListNode(carry % 10);
 carry /= 10;
 a = a->next;
 

 if (carry)
 p->next = new ListNode(carry);

 return dummy->next;
 
 catch (...) 
 p = dummy->next;
 while (p) 
 auto x = p->next;
 delete p;
 p = x;
 
 throw;
 

First: split it up in multiple methods.

Second: You can resuse parts of your code: f(l1->next == NULL && l2->next != NULL) and if(l2->next == NULL && l1->next != NULL) will be identical if l1and l2 are interchanged.

Why do ypu initialise ListNode with 0 or 1 and later reassign the value with the sum of digits? This can be done at once.

When only one list still contain digits the handling can be simplified by specialisation.

Personally I dislike variables like l1, l2, l3 especially as l and 1 can be hard to distinguish.

With the above mentioned I tried to restructure your code (without testing for Bugs introduced by me) to clarify my proposals.

struct ListNode 
 ListNode* next;
 int val;

 ListNode(int arg) next = nullptr; val = arg; 
;

ListNode* addTwoNumbers(ListNode* node1, ListNode* node2)

 if (node1->next != nullptr && node2->next != nullptr)
 
 return addTwoNodes(node1, node2);
 

 else if (node1->next == nullptr && node2->next != nullptr)
 
 return addOneNode(node1->val, node2);
 

 else if (node2->next == nullptr && node1->next != nullptr)
 
 return addOneNode(node2->val, node1);
 

 else 
 return addTwoDigits(node1->val, node2->val);
 


ListNode* addTwoNodes(ListNode* node1, ListNode* node2)

 ListNode *result = new ListNode(node1->val + node2->val);
 if (result->val > 9)
 
 result->val -= 10;
 ListNode tmp(1);
 if (node1->next != nullptr)
 
 ListNode const * const next = node1->next;
 tmp.val += next->val;
 tmp.next = next->next;
 
 result->next = addTwoNumbers(&tmp, node2->next);
 
 else
 
 result->next = addTwoNumbers(node1->next, node2->next);
 
 return result;


ListNode* addOneNode(int val, ListNode* node)

 ListNode *result = new ListNode(val + node->val);
 if (result->val > 9)
 
 result->val -= 10;
 result->next = addOneNode(1, node->next);
 
 else
 
 ListNode *tmp = result;
 for (ListNode *arg = node->next; arg != nullptr; arg = arg->next)
 
 result->next = new ListNode(arg->val);
 
 
 return result;


ListNode* addTwoDigits(int val1, int val2)

 ListNode *result = new ListNode(val1 + val2);

 if (result->val > 9)
 
 result->val -= 10;
 result->next = new ListNode(1);
 
 return result;

I'd suggest that you write down the logic in plain English before turning it into code.


To add two lists:
* Add the first digits
* If the sum is less than ten:
* Store the sum
* Add the rest of the lists
else
* Subtract ten
* Store the sum (after subtraction)
* Add the rest of the lists with the carried ten
Keep going until you've run out digits in both lists.


With a written plan in front of you, you'll find it easier to structure your code clearly and keep it short.

Think carefully about the "contract" of your function: what exactly should the output of addTwoNumbers look like? In your code, the line if(l3->next->val>9) is a red flag: it should not be possible to store numbers bigger than 9 in a node!

Now a couple of sneaky tricks to make it easier:

Remember those boolean circuit design classes where you learned about a binary "half adder" and then a "full adder"? So you have an "add" function and an "add with carry" function. But C++ allows default arguments, so you can roll them into a single function (if the carry isn't specified, it defaults to zero).

Instead of having "if this is null" checks in multiple places in your function, you can put that logic into a helper function, and have it treat nulls as zeros.

(Note: I don't use C++ professionally--I'm writing more from the perspective of algorithm design, not language features, and Deduplicator warns us in the comments that pointers are tricky!--if you wanted to use this in a production system, there's a bit more work to be done.)

Putting it all together, I get this version:

#include <iostream>
using namespace std;

struct Digits 
 Digits* next_node;
 int value;

 Digits(int arg) 
 if (arg < 10) value = arg; next_node = nullptr; 
 else value = arg % 10; next_node = new Digits(arg/10); 
 
;

int valueOrZero(Digits* node) return node==nullptr ? 0 : node->value; 

Digits* nextOrNull(Digits* node) return node==nullptr ? nullptr : node->next_node; 

string digitsToString(Digits* node) 
 return node==nullptr ? "" : digitsToString(node->next_node) + to_string(node->value);



Digits* addTwoNumbers(Digits* node1, Digits* node2, int carry=0)

 if ((node1==nullptr) & (node2==nullptr)) 
 return(new Digits(carry));
 
 else 
 int tens=0;
 int ones = valueOrZero(node1) + valueOrZero(node2) + carry;
 if (ones >= 10) 
 tens = ones/10;
 ones = ones % 10;
 
 Digits* answer = new Digits(ones);
 answer->next_node = addTwoNumbers(nextOrNull(node1), nextOrNull(node2), tens);
 return answer;
 



void testAdd(int val1, int val2) 
 Digits *num1 = new Digits(val1);
 Digits *num2 = new Digits(val2);
 Digits *num3 = addTwoNumbers(num1, num2);
 cout << digitsToString(num1) << "+" << digitsToString(num2) << " = " << digitsToString(num3) << endl;
 


int main(int argc, char* argv) 
 testAdd(1,1);
 testAdd(8,9);
 testAdd(23,8);
 testAdd(999,25);