## Add up two linked list representations of numbers

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)
carryNext));
else if (head1 == null)
else
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;
}

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

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c91028f5f48a', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c91028f5f4bd',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c91028f5f4c0',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. Lei
May 11, 2012 @ 09:08:54

Hi 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:47

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

2. matthew
Oct 04, 2012 @ 23:08:08

your code does not seem to run for me in eclipse.

• Runhe Tian
Oct 04, 2012 @ 23:40:00

What error does it produce?

3. Jack
Feb 01, 2014 @ 17:08:52

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

4. kinshuk4
May 06, 2014 @ 16:41:57

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

5. Juned
Jul 26, 2014 @ 16:34:22

Jack 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)