## Similar Problems

Similar Problems not available

# Add Two Numbers - Leetcode Solution

LeetCode: Add Two Numbers Leetcode Solution

Difficulty: Medium

Topics: math linked-list

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:

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

Solution:

One way to solve this problem is to traverse the two linked lists simultaneously, adding the corresponding nodes and maintaining a carry variable. We create a new linked list whose nodes contain the digits of the sum. We start with the least significant digits and progress towards the most significant digits.

Algorithm:

- Initialize a pointer curr to head of a new linked list
- Initialize variables carry, sum to 0
- Traverse the two linked lists simultaneously until either of them becomes null
- Add the values of the current nodes and the carry variable
- Calculate the sum and the carry by dividing the sum by 10
- Create a new node with the value of the least significant digit of the sum
- Set the next pointer of the current node to the new node
- Move the pointers of both the linked lists to the next nodes
- When the iteration ends, if the carry is non-zero, create a new node with the carry as its value and set its next pointer to null
- Return the head of the new linked list

Code:

```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* curr = head;
int carry = 0;
int sum = 0;
while (l1 != NULL || l2 != NULL) {
int x = (l1 != NULL) ? l1->val : 0;
int y = (l2 != NULL) ? l2->val : 0;
sum = x + y + carry;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (l1 != NULL) l1 = l1->next;
if (l2 != NULL) l2 = l2->next;
}
if (carry > 0) {
curr->next = new ListNode(carry);
}
return head->next;
}
};
```

Time Complexity:

Traversing the two linked lists takes O(max(m, n)) time, where m and n are the lengths of the linked lists. Creating a new linked list takes O(max(m, n)) time as well. Therefore, the time complexity of the solution is O(max(m, n)).

Space Complexity:

We create a new linked list whose length is at most max(m, n) + 1. Therefore, the space complexity of the solution is O(max(m, n)).

## Add Two Numbers Solution Code

`1`