# LeetCode 2. Add Two Numbers

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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

## Explanation

The question is about performing math addition operation with two linked lists. Each node of the result linked list gets value from the sum of two input linked lists. We can just take this process as we are doing addition in columns.

Key point: We need to add a carry just as we do addition in arithmetic. A carry is a digit that is transferred from one column of digits to another column of more significant digits.

For different cases:

• If there are remaining nodes (l1, l2) in both two linked lists, the result linked list node gets value from ((l1.val + l2.val + carry) % 10).
• If there is only one linked list has remaining node, the esult linked list node gets value ((l1.val + carry) % 10 or (l2.val + carry) % 10).
• If neither of linked list has remaining nodes, we should check if there is still carryover value.

## Java Solution

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;

while (l1 != null && l2 != null) {
int value = (l1.val + l2.val + carry) % 10;
carry = (l1.val + l2.val + carry) / 10;
ListNode result = new ListNode(value);
current.next = result;
l1 = l1.next;
l2 = l2.next;
current = result;
}

while (l1 != null) {
int value = (l1.val + carry) % 10;
carry = (l1.val + carry) / 10;
ListNode result = new ListNode(value);
current.next = result;
l1 = l1.next;
current = result;
}

while (l2 != null) {
int value = (l2.val + carry) % 10;
carry = (l2.val + carry) / 10;
ListNode result = new ListNode(value);
current.next = result;
l2 = l2.next;
current = result;
}

if (carry != 0) {
ListNode result = new ListNode(carry);
current.next = result;
current = result;
}

return dummy.next;
}
}```

## Python Solution

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

dummy = ListNode(0)
current = dummy
carry = 0
while l1 != None and l2 != None:

new_node_value = (l1.val + l2.val + carry) % 10
new_node = ListNode(new_node_value)
carry = (l1.val + l2.val + carry) // 10

current.next= new_node
current = current.next
l1 = l1.next
l2 = l2.next

while l1 != None:

new_node_value = (l1.val + carry) % 10
new_node = ListNode(new_node_value)
carry = (l1.val + carry) // 10

current.next= new_node
current = current.next
l1 = l1.next

while l2 != None:

new_node_value = (l2.val + carry) % 10
new_node = ListNode(new_node_value)
carry = (l2.val + carry) // 10

current.next= new_node
current = current.next
l2 = l2.next

if carry != 0:
new_node_value = (carry) % 10
new_node = ListNode(new_node_value)

current.next= new_node
current = current.next

return dummy.next``````