Solving the 'Add Two Numbers' problem on LeetCode with C++
Tags: leetcode
Published: 2023-06-22 10:39:05

## Problem
https://leetcode.com/problems/add-two-numbers/description/

## Answer
```
/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next; 
```

Firstly, let's consider the expected output.
```
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
```

We can obtain the output by summing the numbers from l1 and l2 in order.
```
2 + 5 = 7
4 + 6 = 10 -> 0 // 4 + 6 = 10. Carry 1 to the next digit and truncate the remaining digits. 
3 + 4 = 7 -> 7 + 1 = 8 // Add 1 carried over from the previous digit.

Output: 7, 0, 8
```

Now we need to represent this operation in the code.
```
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 
```
We define `dummy` as a variable of type `ListNode*` because the function result is `ListNode*`.

We define the `temp` variable to reference the dummy pointer, because we need to reference each node to sum each digit.

We define the `carry` variable to store the carried over number.

```
        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
```
We need to calculate all `l1` and `l2` numbers.
This means we must continue calculation until `l1` and `l2` are `NULL` and `carry` is 0.

If `l1` is not `NULL`, we add the value of `l1` to the sum variable.
We move the `l1` pointer to the next pointer because the current `l1` value has been calculated.

We do the same for `l2`.
```
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next; 
```
If there's a `carry` from a previous digit, we need to add it to the sum variable and update `carry` with the new value that needs to be carried over to the next digit.

The first digit of the sum should be assigned to a new Node, and this new Node should be assigned to `temp->next`.
This adds the new Node to the dummy ListNode, but we don't assign the new Node to `dummy->next` directly.

Because `dummy` and `temp` have same pointer.

The reason for this is that we need to return the head of the new ListNode at the end of the function.
 
Here, `temp` is a pointer used for calculating `l1` and `l2`, and `dummy` is a pointer used to return the head of the new ListNode.