# How To Add Two Numbers Represented As Linked Lists

## By iterating digit by digit, and calculating the sum and carry, it handles scenarios for the lengths of the input lists and any remaining carry values

### Problem statement

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.

#### Example 1

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

#### Example 2

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

#### 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]
```

#### Constraints

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: Addition With Remember

Perform the school addition calculation and store the result in one of the lists.

Without loss of generality, let us store the result in `l1`

. Then you might need to extend it when `l2`

is longer than `l1`

and when the result requires one additional node (Example 3).

#### Code

```
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode prehead; // dummy node to hook the head of the list
ListNode* node = l1; // store result on l1
prehead.next = node;
int sum = 0;
while (node) {
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
node->val = sum % 10;
sum /= 10;
if (!l1) { // l1 ends
if (l2) { // l1 is shorter than l2
node->next = l2;
} else if (sum == 1) { // both l1 and l2 end but the remember is not zero
ListNode* newNode = new ListNode(sum);
node->next = newNode;
}
}
node = node->next;
}
return prehead.next;
}
void printResult(ListNode* l) {
std::cout << "[";
while (l) {
std::cout << l->val << ",";
l = l->next;
}
std::cout << "]\n";
}
int main() {
{
ListNode three(3);
ListNode four1(4, &three);
ListNode two(2, &four1);
ListNode four2(4);
ListNode six(6, &four2);
ListNode five(5, &six);
printResult(addTwoNumbers(&two, &five));
}
{
ListNode zero1(0);
ListNode zero2(0);
printResult(addTwoNumbers(&zero1, &zero2));
}
{
ListNode nine0(9);
ListNode nine1(9, &nine0);
ListNode nine2(9, &nine1);
ListNode nine3(9, &nine2);
ListNode nine4(9, &nine3);
ListNode nine5(9, &nine4);
ListNode nine6(9, &nine5);
ListNode nine7(9);
ListNode nine8(9, &nine7);
ListNode nine9(9, &nine8);
ListNode nine10(9, &nine9);
printResult(addTwoNumbers(&nine6, &nine10));
}
}
```

```
Output:
[7,0,8,]
[0,]
[8,9,9,9,0,0,0,1,]
```

This solution efficiently adds two numbers represented as linked lists by iterating through both linked lists, digit by digit, and calculating the sum and carry. It also handles different scenarios for the lengths of the input lists and any remaining carry values.

#### Complexity

Runtime:

`O(N)`

, where`N = max(l1.length, l2.length)`

.Extra space:

`O(1)`

.

Thanks for reading! **Get my book "10 Classic Coding Challenges"** for FREE.