static LNode addTwoList(LNode l1, LNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
int sum = 0, carry = 0;
LNode l = null, head = null;
for(; l1 != null || l2 != null; )
{
sum = carry;
if(l1 != null){
sum = sum + l1.val;
l1 = l1.next;
}
if(l2 != null){
sum = sum + l2.val;
l2 = l2.next;
}
carry = sum / 10;
if(l == null){
l = new LNode(sum%10);
head = l;
}
else {
l.next = new LNode(sum%10);
l = l.next;
}
sum = 0;
}
if(carry > 0)
{
l.next = new LNode(carry);
}
return head;
}
SOLUTION
It's useful to remember in this problem how exactly addition works. Imagine the
problem:
6 1 7
+ 2 9 5
First, we add 7 and 5 to get 12. The digit 2 becomes the last digit of the number, and 1
gets carried over to the next step. Second, we add 1,1, and 9 to get 11 .The 1 becomes
the second digit, and the other 1 gets carried over the final step. Third and finally, we
add 1,6 and 2 to get 9. So, our value becomes 912.
We can mimic this process recursively by adding node by node, carrying over any
"excess"data to the next node. Let's walkthrough this for the below linked list:
7 -> 1 -> 6
+ 5 -> 9 -> 2
We do the following:
1. We add 7 and 5 first, getting a result of 12.2 becomes the first node in our linked list
and we "carry" the 1 to the next sum.
List: 2 -> ?
2. We then add 1 and 9, as well as the "carry," getting a result of 11. 1 becomes the
second element of our linked list, and we carry the 1 to the next sum.
List: 2 -> 1 -> ?
3. Finally, we add 6, 2 and our "carry," to get 9. This become the final element of our
linked list.
List: 2 -> 1 -> 9.
The code below implements this algorithm.
1 LinkedListNode addLists(LinkedListNode 11, LinkedListNode 12,
2 int carry) {
3 /* We're done if both lists are null AND the carry value is 0 */
4 if (11 == null && 12 == null && carry == 0) {
5 return null;
6 }
7
8 LinkedListNode result = new LinkedListNode(carry, null, null);
9
10 /* Add value, and the data from 11 and 12 */
11 int value = carry;
12 if (11 != null) {
13 value += 11.data;
14 }
15 if (12 != null) {
16 value += 12.data;
17 }
18
19 result.data = value % 10; /* Second digit of number */
20
21 /* Recurse */
if (11 != null || 12 != null) {
23 LinkedListNode more = addLists(ll == null ? null : 11.next,
24 12 == null ? null : 12.next,
25 value >= 10 ? 1 : 8);
26 result.setNext(more);
}
28 return result;
29 }
In implementing this code, we must be careful to handle the condition when one linked
list is shorter than another. We don't want to get a null pointer exception.
