We’re going to be discussing Add Two Numbers Leetcode Solution in Python which is a Leetcode Medium Problem (#2).

The “Add Two Numbers” problem on LeetCode presents an interesting challenge of adding two non-negative integers represented by linked lists. The digits of these numbers are stored in reverse order, and each node in the linked list contains a single digit. The task is to perform the addition and return the result as a linked list.

## Table of Contents

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

**Leetcode Problem Link**: https://leetcode.com/problems/add-two-numbers/

## Solution

### BruteForce Approach

#### Details:

**Convert to Number:**The linked lists are traversed to convert each digit into an integer, and the two resulting integers are summed.**Perform Addition:**The sum is then converted back into a linked list, with each digit represented by a node.

#### Summary:

- The brute force solution involves converting linked lists to integers, performing addition, and then converting the result back to a linked list.
- The time complexity is dominated by the conversion steps, making it less efficient for large numbers.

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbersBruteForce(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
num1 = self.convert_to_number(l1)
num2 = self.convert_to_number(l2)
result = num1 + num2
return self.convert_to_linked_list(result)
def convert_to_number(self, node):
result = 0
multiplier = 1
while node:
result += node.val * multiplier
multiplier *= 10
node = node.next
return result
def convert_to_linked_list(self, number):
dummy = ListNode()
current = dummy
for digit in str(number)[::-1]:
current.next = ListNode(int(digit))
current = current.next
return dummy.next
```

#### Time Complexity:

- Conversion to Number: O(n) where n is the length of the longer linked list.
- Conversion to Linked List: O(m) where m is the number of digits in the sum.

### Optimal Approach

#### Details:

**Two-Pointer Iteration:**Similar to the better solution, two pointers traverse both linked lists simultaneously.**Perform Addition:**Addition is performed digit by digit, considering any carry from the previous step.**Create Result List:**The result is constructed in-place, and a new linked list is returned.

#### Summary:

- The optimal solution shares similarities with the better solution but minimizes the use of variables and combines the addition logic with the iteration.
- It maintains efficiency and handles edge cases effectively.

```
class Solution:
def addTwoNumbersOptimal(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
current = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
total_sum = x + y + carry
carry, digit = divmod(total_sum, 10)
current.next = ListNode(digit)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
```

#### Time Complexity:

- Iterating Through Lists: O(max(n, m)) where n and m are the lengths of the input linked lists.

So these two were the brute and optimal solutions for add two numbers leetcode problem in python. I hope you got a good understanding of the solution and will be able to solve this problem upon iterations.

**Something You Might Like:**

## Leave a Reply