4
\$\begingroup\$

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

    }
}
\$\endgroup\$
10
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ The obvious flaws are error-handling and different length numbers. \$\endgroup\$ – Deduplicator Mar 30 '18 at 13:24
  • \$\begingroup\$ @Deduplicator, it's not obvious to me what you're referring to in your comment. Would you mind giving a little more detail? \$\endgroup\$ – Alexander Hanysz Mar 31 '18 at 12:50
  • \$\begingroup\$ Well, what happens if one of the allocations fails, maybe not the first? What happens if one number is longer than the other? Also, do you know that calling a member-function using a null-pointer is UB, so this != nullptr always holds? \$\endgroup\$ – Deduplicator Mar 31 '18 at 13:07
  • \$\begingroup\$ Thanks for the feedback re this!=nullptr. It worked on my platform, and I didn't realise it wasn't portable. What happens if one number is longer than the other? Answer: I tested it and there's no problem here. What if the allocations fail? Yes, that's bad news. I'm just giving some short code to illustrate a point about algorithm design, not trying to write robust enterprise software here. The OP didn't ask about error handling, and the other answers didn't address it either. \$\endgroup\$ – Alexander Hanysz Apr 1 '18 at 0:41
  • \$\begingroup\$ Edited to avoid accessing member functions through null pointers -- I've moved these checks into helper functions. Hopefully no undefined behaviour now. @Deduplicator, do you mind taking another look at it? \$\endgroup\$ – Alexander Hanysz Apr 2 '18 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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