Appearance

# Add Two Numbers Medium

## Question

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 contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

txt

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

txt

```
Input: l1 = [0], l2 = [0]
Output: [0]
```

txt

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

txt

```
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
```

## Solution

python

```
def addTwoNumbers(l1, l2):
dummy_head = ListNode(0)
current = dummy_head
carry = 0
while l1 or l2 or carry:
sum_val = carry
if l1:
sum_val += l1.val
l1 = l1.next
if l2:
sum_val += l2.val
l2 = l2.next
carry = sum_val // 10
current.next = ListNode(sum_val % 10)
current = current.next
return dummy_head.next
```

java

```
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode current = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}
return dummyHead.next;
}
```

javascript

```
function addTwoNumbers(l1, l2) {
const dummyHead = new ListNode(0);
let current = dummyHead;
let carry = 0;
while (l1 || l2 || carry) {
let sum = carry;
if (l1) {
sum += l1.val;
l1 = l1.next;
}
if (l2) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
}
return dummyHead.next;
}
```

## Notes

In this problem, we are given two linked lists representing non-negative integers, where each node contains a single digit, and the digits are stored in reverse order. Our goal is to add the two numbers and return the sum as a new linked list.

### Definition of ListNode:

Before we proceed with the solutions, we'll define the ListNode class in all three languages to represent the nodes of the linked list.

python

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```

java

```
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;
}
}
```

javascript

```
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
```

### Solution Explanation:

We'll traverse both linked lists simultaneously, summing the corresponding digits and handling carry if present. The sum of two digits can be greater than 9, in which case we need to carry the extra digit to the next node.

We'll initialize a dummy node to keep track of the head of the result linked list and two pointers to traverse the input linked lists. As we iterate through the lists, we'll add the values of the nodes and the carry (if any) to compute the sum at the current position.

### Time Complexity:

The time complexity of the solution is O(max(m, n)), where m and n are the lengths of the two input linked lists. We need to traverse both lists to calculate the sum, and the length of the resulting linked list is at most max(m, n) + 1.

### Space Complexity:

The space complexity of the solution is O(max(m, n)). It's because we create a new linked list to store the result, and the length of the resulting linked list is at most max(m, n) + 1, where m and n are the lengths of the input linked lists. Additionally, we use a constant amount of extra space for variables `current`

and `carry`

.