You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE

Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

**My initial thoughts:**

Add up numbers nodes by nodes. Take care of carries. In each summation of two digits:

sum digit = (digit1 + digit2 + carry_from_previous) % 10;

carry = (digit1 + digit2 + carry_from_previous) – 10;

There are generally three cases needed to be handled:

- digit1 and digit2 are neigher null
- digit1 is null
- digit2 is null

**My initial codes:**

public static LLNode<Integer> addWithCarry(LLNode<Integer> head1,
LLNode<Integer> head2, boolean carry) {
if (head1 == null && head2 == null) {
LLNode<Integer> node = carry ? new LLNode<Integer>(1) : null;
return node;
}
int number1 = head1 == null ? 0 : head1.getData();
int number2 = head2 == null ? 0 : head2.getData();
int sum = carry ? (number1 + number2 + 1) % 10
: (number1 + number2) % 10;
boolean carryNext = carry ? number1 + number2 + 1 >= 10
: (number1 + number2) >= 10;
LLNode<Integer> node = new LLNode<Integer>(sum);
if (head1 != null && head2 != null)
node.setNext(addWithCarry(head1.getNext(), head2.getNext(),
carryNext));
else if (head1 == null)
node.setNext(addWithCarry(null, head2.getNext(), carryNext));
else
node.setNext(addWithCarry(head1.getNext(), null, carryNext));
return node;
}

**Solution**

public static LLNode<Integer> addList(LLNode<Integer> l1,
LLNode<Integer> l2, int carry) {
if (l1 == null && l2 == null)
return null;
LLNode<Integer> result = new LLNode<Integer>(carry);
int value = carry;
if (l1 != null)
value += l1.getData();
if (l2 != null)
value += l2.getData();
result.setData(value % 10);
LLNode<Integer> more = addList(l1 == null ? null : l1.getNext(),
l2 == null ? null : l2.getNext(), value > 10 ? 1 : 1);
result.setNext(more);
return result;
}

Comments:

There are two mistakes in this solution. Highlighted line 4. If l1 and l2 are both null, you still need to consider the carry: 1 + 9->1 = 0->0->1 but this solution will output 0->0. Highlighted line 13: should be:

value >= 10 ? 1 : 0

### Like this:

Like Loading...

*Related*

Lei

May 11, 2012@ 09:08:54Hi Runhe,

Your solution looks correct to me, but I have a question here, why do you use

recursive way here?

Runhe Tian

May 11, 2012@ 11:50:47Hi Lei, recursion seems natural to me. You can definitely use loops. Any recursion method can be rewritten as loops. But that won’t reduce the time complexity and it’s a little bit harder to write for this problem.

matthew

Oct 04, 2012@ 23:08:08your code does not seem to run for me in eclipse.

Runhe Tian

Oct 04, 2012@ 23:40:00What error does it produce?

Jack

Feb 01, 2014@ 17:08:52Line 4 is actually correct. Since it’s a recursive call, the “return null” here simply sets the “next” of the last element in the result list to be “null”, which is correct. I do agree that line 13 is wrong though.

kinshuk4

May 06, 2014@ 16:41:57Liked your solution man, good to see recursive solution. Here is my iterating solution from http://k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html:

node *long_add(mynode *h1, mynode *h2, mynode *h3) //h3 = h2+h1

{

node *c, *c1, *c2;

int sum, carry, digit;

carry = 0;

c1 = h1->next;

c2 = h2->next;

while(c1 != h1 && c2 != h2)

{

sum = c1->value + c2->value + carry;

digit = sum % 10;

carry = sum / 10;

h3 = insertNode(digit, h3);

c1 = c1->next;

c2 = c2->next;

}

if(c1 != h1)

{

c = c1;

h = h1;

}

else

{

c = c2;

h = h2;

}

while(c != h)

{

sum = c->value + carry;

digit = sum % 10;

carry = sum / 10;

h3 = insertNode(digit, h3);

c = c->next;

}

if(carry==1)

{

h3 = insertNode(carry, h3);

}

return(h3);

}

Juned

Jul 26, 2014@ 16:34:22Jack is wrong about line 4. Tian you are correct about missing to consider the carry:

I guess if you replace line 3 with below it just works fine then

if (l1 == null && l2 == null && carry ==0)