# Add Two Numbers

MediumLeetCodeLinked ListMathRecursion

This problem involves adding two numbers represented by linked lists.

You can find the original problem described on LeetCode.

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

## Problem Solving

There are a few ways to solve this problem. I will explain all of them to you in the next sections. ๐จโ๐ซ

Before that, below is the definition of `ListNode`

by LeetCode, which we’re going to use on every solution.

```
public class ListNode {
public var val: Int
public var next: ListNode? = nil
public init(_ val: Int) {
self.val = val
}
public init(_ val: Int, _ next: ListNode?) {
self.val = val
self.next = next
}
}
```

### Iterative method

The iterative method involves traversing both linked lists, adding corresponding digits along with any carry-over from the previous addition.

```
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
// Dummy head to handle corner case (we return the next node)
let dummyHead = ListNode(0)
// This is the pointer we will use to construct the new list
var currentNode: ListNode? = dummyHead
// These pointers will navigate through the nodes
var p1 = l1
var p2 = l2
// No initial carry value
var carry = 0
// Iterate until we reach the end of both lists
while p1 != nil || p2 != nil {
// Sum of the current values and carry
let sum = carry + (p1?.val ?? 0) + (p2?.val ?? 0)
// New carry
carry = sum / 10
// New node with the unit digit
currentNode?.next = ListNode(sum % 10)
// Move to the next nodes
currentNode = currentNode?.next
p1 = p1?.next
p2 = p2?.next
}
// Add a new node if there's a carry left
if carry > 0 {
currentNode?.next = ListNode(carry)
}
// Return the head of the new list (ignore the dummy head)
return dummyHead.next
}
```

### Recursive method

This method solves the problem with a few less lines of code, with the use of recursion to move through the list nodes.

```
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
// Start by calling the helper with the initial carry (zero)
addTwoNumbers(l1, l2, 0)
}
private func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?, _ carry: Int) -> ListNode? {
// Base case: return nil if we reach the end of both lists and carry is zero
guard l1 != nil || l2 != nil || carry > 0 else { return nil }
// Sum of the current values and carry
let sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
// New node with the unit digit
let resultNode = ListNode(sum % 10)
// Recursively add the next node with the new carry
resultNode.next = addTwoNumbers(l1?.next, l2?.next, sum / 10)
// Return the resulting node
return resultNode
}
```

This solution looks pretty good, with just a few lines of code. But can we have an even better solution? ๐ค

### Recursive method (improved)

We can improve that previous solution if we could stop the recursion earlier, once we reach the end of either one of the lists.

Let me show you how to do it. ๐จโ๐ซ

```
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
// Base cases: return the other list if one is nil (empty)
guard let l1 else { return l2 }
guard let l2 else { return l1 }
// Sum of current nodes
let sum = l1.val + l2.val
// New node with the unit digit
let resultNode = ListNode(sum % 10)
// Recursively add the next node
let nextNode = addTwoNumbers(l1.next, l2.next)
if sum > 9 {
// If the sum is greater than 9, carry 1 to the new node
resultNode.next = addTwoNumbers(nextNode, ListNode(1))
} else {
// Otherwise, there is no carry
resultNode.next = nextNode
}
// Return the resulting node
return resultNode
}
```

## Complexity Analysis

### Time Complexity

Both iterative and recursive methods have the same time complexity: `O(max(m, n))`

, where `m`

and `n`

are the number of nodes in each list. This is because they both go through all of the nodes in both lists, one by one, at the same time.
The *“improved recursive”* version works similar, but will stop earlier in case one list is shorter, so the time complexity is `O(min(m, n))`

. However, if both lists have the same size, all solutions will end with the same `O(n)`

(since `m == n`

in this case).

### Space Complexity

All the solutions use the same `O(1)`

constant space. This is because we are only manipulating pointers and not creating any extra space. The total space for each solutions is `O(max(m, n))`

. In some cases, also `O(max(m, n) + 1)`

, if there will be a carry at the end.

## Conclusion

All solutions described here, whether they are iterative or recursive, are good enough providing a comprehensive understanding of different approaches to solving this problem.

The *“improved recursive”* version might have a slight advantage when it comes to time complexity, since it could finish earlier.

But in worst case scenarios (when both lists are the same size, for instance), they all will have the same time and space complexities.

Also, while the recursive method handles the problem elegantly by breaking it down into smaller subproblems, it has potential drawbacks, particularly concerning the recursion depth and stack overflow.

So keep all these things in mind when experimenting with these different options. ๐งโ๐ฌ

**Check all problem solutions and run the test cases easily with LeetSwift! ๐**

**Get fresh, exclusive content delivered right to your inbox every week ๐ฌโจ**