DAY 94 - Add Two Numbers
Tags: leetcode, algorithms, beginners, codenewbie
Published: 2023-09-05 16:47:19

Let's solve one of the most famous leetcode questions today which is about adding two numbers in a linked list.

## Analyzing [Add Two Numbers"](https://leetcode.com/problems/add-two-numbers/) Problem

_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:


![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bmal05f6n8b0j92t3qlj.png)

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

---

## Understanding the Problem

Before diving into the code, let's break down the problem and understand what's expected:

- You're given two linked lists, `l1` and `l2`, where each node contains a digit.

- The digits are stored in reverse order. That means the 1's digit is at the head of the list, followed by the 10's digit, and so on.

- Your task is to add these two numbers and return the result as a linked list.

## The Approach

To solve this problem, we can use a simple iterative approach that resembles how we manually add numbers. Here's the intuition behind the approach:

1. **Initialize Variables**: We start by initializing some variables. We'll maintain two pointers, `temp1` and `temp2`, to traverse `l1` and `l2`, respectively. We also initialize a `carry` variable to handle carryovers during addition.

2. **Initialize the Result List**: We create a new linked list called `ans` to store the result. Additionally, we keep a pointer called `start` to the current node in the `ans` list.

3. **Iterate Through the Lists**: We use a `while` loop that continues until both `temp1` and `temp2` reach the end of their respective lists. In each iteration, we perform the following steps:

   - Extract the values `val1` and `val2` from the current nodes `temp1` and `temp2`, respectively. If either of the lists has reached its end, we consider the value as 0.

   - Calculate the sum of `val1`, `val2`, and the `carry` from the previous step.

   - Update the current node in the result list (`start`) with the last digit of the sum (`sum % 10`) and calculate the carry for the next iteration (`carry = sum / 10`).

   - Move `temp1` and `temp2` to their respective next nodes, if available.

   - If there are more digits in either `l1` or `l2`, or if there's a carry from the last addition, we create a new node in the result list and move the `start` pointer to this new node.

4. **Handle Any Remaining Carry**: After the loop, if there's still a carry (which could happen if the last addition results in a carry), we create one final node in the result list to accommodate the carry.

5. **Return the Result**: Finally, we return the `ans` linked list, which represents the sum of the two input numbers.


## Code:

```cpp

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* temp1 = l1;
        ListNode* temp2 = l2;
        ListNode* ans = new ListNode();
        ListNode* start = ans;

        while (temp1 || temp2) {
            int val1 = (temp1) ? temp1->val : 0;
            int val2 = (temp2) ? temp2->val : 0;
            
            int sum = val1 + val2 + carry;
            
            start->val = sum % 10;
            carry = sum / 10;
            
            if (temp1) temp1 = temp1->next;
            if (temp2) temp2 = temp2->next;
            
            if (temp1 || temp2 || carry > 0) {
                start->next = new ListNode();
                start = start->next;
            }
        }

        if (carry > 0) {
            start->val = carry;
        }

        return ans;
    }
};



```

## Time and Space Complexity

Let's analyze the time and space complexity of our solution:

- **Time Complexity**: The algorithm makes a single pass through both input lists, so its time complexity is O(max(N, M)), where N and M are the lengths of `l1` and `l2`, respectively.

- **Space Complexity**: We create a new linked list to store the result, which takes O(N) space where N is the greater value.