## Introduction

LeetCode Problem 2, “Add Two Numbers,” is a popular problem that involves linked lists. The problem can be summarized as follows:

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

### Examples:

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

## Possible Solutions

### Approach 1: Iterative Method

#### Algorithm:

- Initialize a dummy head to help with the resulting linked list.
- Initialize a
`current`

pointer to the dummy head and a carry variable to 0. - Iterate through both linked lists until both are exhausted and there is no carry left:
- Sum the current digits of both lists along with the carry.
- Update the carry.
- Create a new node with the sum modulo 10.
- Move the
`current`

pointer and the pointers of the input lists to their next nodes.

- Return the linked list starting from the node next to the dummy head.

#### Time and Space Complexity:

**Time Complexity:**O(max(m, n)), where m and n are the lengths of the two linked lists. We traverse both lists at most once.**Space Complexity:**O(max(m, n)), which is the space for the resulting linked list.

### Python Code:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
dummy_head = ListNode()
current = dummy_head
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy_head.next
One of the fastest solution in terms of run time is below:
# 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]:
op = opHead = ListNode()
s = 0
while l1 or l2 or s:
op.next = ListNode()
op = op.next
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
s, op.val = divmod(s, 10)
l1 = l1.next if l1 else False
l2 = l2.next if l2 else False
return opHead.next
```

## Edge Cases

### Edge Case 1: Different Lengths of Lists

**Example:**l1 = [2, 4], l2 = [5, 6, 4]**Explanation:**The algorithm will handle lists of different lengths by treating the missing nodes as zero.

### Edge Case 2: Carry at the End

**Example:**l1 = [9, 9], l2 = [1]**Explanation:**The sum is 100, so the output should be [0, 0, 1]. The algorithm adds an additional node if there is a carry left after processing both lists.

### Edge Case 3: One List is Empty

**Example:**l1 = [], l2 = [0, 1]**Explanation:**The algorithm treats the empty list as zero and returns the non-empty list.

### Edge Case 4: Both Lists are Empty

**Example:**l1 = [], l2 = []**Explanation:**The algorithm should handle this by returning a single node with value 0.

### Handling Edge Cases in Code

```
def addTwoNumbers(l1, l2):
dummy_head = ListNode()
current = dummy_head
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy_head.next
# Test cases for edge cases
# Case 1: Different lengths
l1 = ListNode(2, ListNode(4))
l2 = ListNode(5, ListNode(6, ListNode(4)))
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [7, 0, 5]
# Case 2: Carry at the end
l1 = ListNode(9, ListNode(9))
l2 = ListNode(1)
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0, 0, 1]
# Case 3: One list empty
l1 = None
l2 = ListNode(0, ListNode(1))
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0, 1]
# Case 4: Both lists empty
l1 = None
l2 = None
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0]
```

To print the linked list in the test cases, you would need a helper function:

```
def print_linked_list(node):
while node:
print(node.val, end=" -> " if node.next else "\n")
node = node.next
```

In conclusion, the iterative method provides an efficient and straightforward way to solve the “Add Two Numbers” problem on LeetCode. By carefully handling edge cases, we ensure the robustness and correctness of our solution.