# Algorithm exercise: adding two numbers

Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number.

You can assume that neither number starts with 0 except the number 0.

Example 1: ```Input: l1 = [2,4,3], l2 = [5,6,4]
Output:[7,0,8]
Explanation: 342 + 465 = 807.
```

Example 2:

```Input: l1 = , l2 = 
Output:
```

Example 3:

```Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output:[8,9,9,9,0,0,0,1]
```

Tips:

• The number of nodes in each linked list is within the range [1, 100]
• 0 <= Node.val <= 9
• The number represented in the title data guarantee list does not contain leading zeros

Related Topics

recursion

mathematics

```//leetcode submit region begin(Prohibit modification and deletion)
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {

1.iteration
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode root = new ListNode(0),cursor = root;
int carry = 0;//Represents carry
while(l1!=null || l2!=null || carry!=0){
int a = l1!=null ? l1.val : 0;//Judge whether the node is empty. If it is empty, directly assign a to 0, which can effectively avoid calling L1 Null pointer exception in val
int b = l2!=null ? l2.val : 0;//Judge whether the node is empty
int sum = a+b+carry;//If the last carry was, the carry is 1
carry = sum/10;

ListNode new_node = new ListNode(sum%10);//Generate a new node
cursor.next = new_node;
cursor = new_node;

if(l1!=null) l1 = l1.next;
if(l2!=null) l2 = l2.next;

}

return root.next;
}
}

2.recursion
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Calculate the sum of two node values
int val = l1.val + l2.val;
// Calculate carry value: whether the sum of two nodes is greater than 10
int carry = val / 10;
// Whether the recursive termination condition is satisfied: there is no next in both stages
if (l1.next == null && l2.next == null) {
// The termination conditions have been met, but there are two cases. Whether the sum of the last two nodes is greater than 10. If it is greater than 10, carry is required. Otherwise, return directly
return val < 10 ? new ListNode(val) : new ListNode(val % 10, new ListNode(carry));
}
// Create a node object. Each node can only save numbers from 0 to 9, so take the remainder of 10
ListNode node = new ListNode(val%10);
// Handle the inconsistency of the length of two linked lists. The linked list with short length shall be supplemented with carry value
if (l1.next == null) {
l1.next = new ListNode(carry);
} else if (l2.next == null) {
l2.next = new ListNode(carry);
} else {
// The two linked lists have next nodes. Add carry to the next node, i.e. + 1,l1 and l2
l1.next.val += carry;
}
// Recursive accumulation
return node;
}

//leetcode submit region end(Prohibit modification and deletion)

```

## Recursive error prone:

​ At first, I created a new variable in the loop, which obviously didn't work. After this cycle, this variable does not exist, so at the beginning, the root linked list is declared to store the head node of the destination linked list, and then a cursor cursor pointer is declared to traverse the whole linked list. The newly created variables in the cycle are also assigned to cursor variables (operated by cursor variables), so that these newly created nodes can exist all the time after the cycle.

## Iteration error prone:

1. The length of the two linked lists may be inconsistent, so the linked list with short length needs to be supplemented with 0 to the same length as the other linked list to avoid null pointer exception due to inconsistent length in the addition process.
2. When the two linked lists are added to the last node, it is necessary to verify whether the carry conditions are met. If the conditions are met, it is necessary to add another bit to save the carry, and then the value of the current node can be taken as the remainder of 10.
3. Be sure to ensure the termination condition of recursion, otherwise you know...