# Add Two Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/add-two-numbers/)
Canonical: https://scaleengineer.com/dsa/problems/add-two-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Avito](https://scaleengineer.com/companies/avito), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [EarnIn](https://scaleengineer.com/companies/earnin), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Commvault](https://scaleengineer.com/companies/commvault), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## 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:**

![](https://assets.glich.co/dsa/add-two-numbers/image0.jpg) 

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

# Approaches
## Convert to Number, Add, and Convert Back
This approach involves converting the two linked lists into their corresponding integer representations. After converting, we add these two numbers together. Finally, the resulting sum is converted back into a linked list in the required reverse-digit format.
**Time:** O(max(N, M)) · **Space:** O(max(N, M))
**Pros:** Conceptually simple to understand if the `BigInteger` class is familiar.; Leverages powerful, built-in arithmetic capabilities.
**Cons:** Suffers from integer overflow if standard integer types like `long` are used. Requires a special class like `BigInteger`.; Less efficient due to the overhead of converting between data structures (list to string, string to BigInteger, BigInteger back to string, and string back to list).; This approach might be considered less fundamental as it abstracts away the core logic of addition into a library function.
### Explanation
The core idea is to transform the linked list representation of numbers into a standard numerical type that the computer can perform arithmetic on directly.

1.  **Convert Linked Lists to Numbers:** We traverse each linked list, `l1` and `l2`. Since the digits are in reverse order, we can build the number by effectively multiplying each digit by its corresponding power of 10. A crucial point is that the numbers can be very large, exceeding the capacity of standard 64-bit integers (`long` in Java). Therefore, we must use a class designed for arbitrary-precision arithmetic, like `java.math.BigInteger`.

2.  **Sum the Numbers:** Once we have the two numbers as `BigInteger` objects, we simply use the `add` method to compute their sum.

3.  **Convert Sum back to Linked List:** We convert the `BigInteger` sum back to a string. We then iterate through this string in reverse to create the new linked list, as the problem requires digits in reverse order. Each character is converted to a digit and placed in a new `ListNode`.

```java
import java.math.BigInteger;

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Step 1: Convert linked lists to BigInteger
        BigInteger num1 = listToBigInt(l1);
        BigInteger num2 = listToBigInt(l2);

        // Step 2: Add the numbers
        BigInteger sum = num1.add(num2);

        // Step 3: Convert sum back to a linked list
        String sumStr = sum.toString();
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        
        // Handle the case of sum being 0
        if (sum.equals(BigInteger.ZERO)) {
            return new ListNode(0);
        }

        for (int i = sumStr.length() - 1; i >= 0; i--) {
            int digit = sumStr.charAt(i) - '0';
            current.next = new ListNode(digit);
            current = current.next;
        }
        
        return dummyHead.next;
    }

    private BigInteger listToBigInt(ListNode node) {
        StringBuilder sb = new StringBuilder();
        while (node != null) {
            sb.insert(0, node.val);
            node = node.next;
        }
        return new BigInteger(sb.toString());
    }
}
```
### Algorithm
- Create a helper function `listToBigInt` that converts a linked list to a `BigInteger`.
- Inside `listToBigInt`, iterate through the list, building a string representation of the number by prepending each digit. This correctly reverses the list order.
- Convert the final string to a `BigInteger`.
- In the main function, call `listToBigInt` for both `l1` and `l2`.
- Use the `add` method of `BigInteger` to compute the sum.
- Convert the resulting `BigInteger` sum back to a string.
- Create a `dummyHead` for the result list.
- Iterate through the sum string from right to left (end to start).
- For each character, parse the digit, create a new `ListNode`, and append it to the result list.
- Return `dummyHead.next`. Handle the edge case where the sum is 0.

## Single Pass Simulation with Carry
This is the optimal approach that mimics how we perform addition by hand. We iterate through both linked lists simultaneously, from the least significant digit (the head of the list) to the most significant, keeping track of a carry-over value.
**Time:** O(max(N, M)) · **Space:** O(max(N, M))
**Pros:** Optimal time complexity as it requires only a single pass through the lists.; Optimal space complexity, using space proportional to the length of the result.; Works for numbers of any size, limited only by memory, as it never converts the entire list to a single number.; It is the standard, most efficient, and direct way to solve the problem.
**Cons:** Requires careful pointer manipulation.; Edge cases like lists of different lengths and a final carry must be handled correctly.
### Explanation
We can solve this problem by directly simulating the grade-school addition algorithm. We'll iterate through the lists together, adding the corresponding digits along with any carry from the previous step. This avoids any number conversion and thus is not limited by the size of standard data types.

1.  Initialize a `dummyHead` node with value 0. This node simplifies the code by providing a fixed entry point to the result list.
2.  Initialize a `current` pointer to `dummyHead`. This pointer will be used to append new nodes to the result list.
3.  Initialize a `carry` variable to 0.
4.  Start a loop that continues as long as there are nodes left in `l1` or `l2`.
5.  Inside the loop, get the values from the current nodes of `l1` and `l2`. If a list has been fully traversed (its pointer is `null`), its value for the current digit is considered 0.
6.  Calculate the `sum` of the two digits and the `carry`.
7.  The new `carry` for the next iteration is `sum / 10`.
8.  The digit to be stored in the new node is `sum % 10`.
9.  Create a new `ListNode` with this digit and attach it to the result list by setting `current.next`.
10. Move the `current` pointer forward to this new node.
11. Move `l1` and `l2` pointers to their next nodes, if they are not null.
12. After the loop, there might be a final carry left (e.g., adding 50 + 50 results in 100). If `carry > 0`, a new node with the carry value must be appended.
13. Finally, return `dummyHead.next`, which is the head of the actual result list.

```java
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, current = dummyHead;
        int carry = 0;
        
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        
        return dummyHead.next;
    }
}
```
### Algorithm
- Initialize a `dummyHead` node to serve as a starting point for the result list and a `current` pointer to build the list.
- Initialize a `carry` variable to 0.
- Loop as long as `l1` is not null, `l2` is not null, or `carry` is not 0.
- Inside the loop, get the values `x` from `l1` (or 0 if `l1` is null) and `y` from `l2` (or 0 if `l2` is null).
- Calculate `sum = x + y + carry`.
- Update the `carry` for the next iteration: `carry = sum / 10`.
- Create a new node with the value `sum % 10` and attach it to the result list (`current.next`).
- Advance the `current` pointer to the newly created node.
- Advance `l1` and `l2` to their next nodes if they are not null.
- After the loop, the sum is fully calculated. Return `dummyHead.next`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode AddTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode (); int carry = 0 ; ListNode cur = dummy ; while ( l1 != null || l2 != null || carry != 0 ) { int s = ( l1 == null ? 0 : l1 . val ) + ( l2 == null ? 0 : l2 . val ) + carry ; carry = s / 10 ; cur . next = new ListNode ( s % 10 ); cur = cur . next ; l1 = l1 == null ? null : l1 . next ; l2 = l2 == null ? null : l2 . next ; } return dummy . next ; } }
```

### Java

```java
/** * Definition for singly-linked list. * 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; } * } */ class Solution { public ListNode addTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode ( 0 ); int carry = 0 ; ListNode cur = dummy ; while ( l1 != null || l2 != null || carry != 0 ) { int s = ( l1 == null ? 0 : l1 . val ) + ( l2 == null ? 0 : l2 . val ) + carry ; carry = s / 10 ; cur . next = new ListNode ( s % 10 ); cur = cur . next ; l1 = l1 == null ? null : l1 . next ; l2 = l2 == null ? null : l2 . next ; } return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers =
  function (l1, l2) {
    const dummy = new ListNode();
    let carry = 0;
    let cur = dummy;
    while (l1 || l2 || carry) {
      const s = (l1?.val || 0) + (l2?.val || 0) + carry;
      carry = Math.floor(s / 10);
      cur.next = new ListNode(s % 10);
      cur = cur.next;
      l1 = l1?.next;
      l2 = l2?.next;
    }
    return dummy.next;
  };

```

### CPP

```cpp
/** * 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 (); int carry = 0 ; ListNode * cur = dummy ; while ( l1 || l2 || carry ) { int s = ( l1 ? l1 -> val : 0 ) + ( l2 ? l2 -> val : 0 ) + carry ; carry = s / 10 ; cur -> next = new ListNode ( s % 10 ); cur = cur -> next ; l1 = l1 ? l1 -> next : nullptr ; l2 = l2 ? l2 -> next : nullptr ; } return dummy -> next ; } };
```

### Python

```python
# 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 : Optional [ ListNode ], l2 : Optional [ ListNode ] ) -> Optional [ ListNode ]: dummy = ListNode () carry , curr = 0 , dummy while l1 or l2 or carry : s = ( l1 . val if l1 else 0 ) + ( l2 . val if l2 else 0 ) + carry carry , val = divmod ( s , 10 ) curr . next = ListNode ( val ) curr = curr . next l1 = l1 . next if l1 else None l2 = l2 . next if l2 else None return dummy . next
```