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.

**Initialize a dummy head of the result list**: This dummy head will serve as the starting point of our result linked list.**Initialize carry to 0**: The carry will take care of any overflow from the addition of two digits.**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.**Handle overflow**: If the sum is greater than 9, we set the carry to 1. Otherwise, we set it to 0.**Continue the process**: We repeat this process until we’ve gone through both lists.**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:
dummy_head = ListNode(0)
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)
return dummy_head.next
```

### JavaScript

```
var addTwoNumbers = function(l1, l2) {
let dummyHead = new ListNode(0);
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);
}
return dummyHead.next;
};
```

## 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 ðŸ˜„

**Learn More:**