# LeetCode #2 – Add Two Numbers

Hello, 👋 Today, we’re going to unravel another interesting problem from LeetCode: “Add Two Numbers” represented as linked lists.

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

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

## Analysis

The task is to add two numbers represented by two linked lists. Each node in the linked list contains a single digit, and the digits are stored in reverse order.

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

## Approach

The most straightforward approach is to traverse both lists and simulate the addition of two numbers.

1. Initialize a dummy head of the result list: This dummy head will serve as the starting point of our result linked list.
2. Initialize carry to 0: The carry will take care of any overflow from the addition of two digits.
3. Loop through lists while there are still nodes left: On each loop iteration, we add the current digits of the two lists together and set it as the next node of the dummy head.
4. Handle overflow: If the sum is greater than 9, we set the carry to 1. Otherwise, we set it to 0.
5. Continue the process: We repeat this process until we’ve gone through both lists.
6. Handle remaining carry: If there’s still a carry after going through both lists, we add a new node with the digit 1.

## Time Complexity

The time complexity for this approach is `O(max(m, n))`, where m and n are the lengths of the two linked lists. This is because we’re processing all the nodes in both lists once.

## Space Complexity

The space complexity is also `O(max(m, n))` because the length of the new list is at most `max(m, n) + 1`.

## Code

Here’s the Python and JavaScript code for this approach:

### Python

``````class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p, q, current = l1, l2, dummy_head
carry = 0

while p is not None or q is not None:
x = p.val if p is not None else 0
y = q.val if q is not None else 0
sum = carry + x + y
carry = sum // 10
current.next = ListNode(sum % 10)
current = current.next
if p is not None: p = p.next
if q is not None: q = q.next
if carry > 0:
current.next = ListNode(carry)

### JavaScript

``````var addTwoNumbers = function(l1, l2) {
let p = l1, q = l2, current = dummyHead;
let carry = 0;

while (p !== null || q !== null) {
let x = (p !== null) ? p.val : 0;
let y = (q !== null) ? q.val : 0;
let sum = carry + x + y;
carry = Math.floor(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);
}
};``````

## Conclusion

In this post, we tackled the “Add Two Numbers” problem from LeetCode using a straightforward approach. This solution has a time complexity of `O(max(m, n))` and a space complexity of `O(max(m, n))`.

Remember, coding is a journey. Keep exploring, keep learning, and most importantly, have fun doing it!

Happy coding 😄 