**Add Two Numbers as Lists**

Difficulty: Medium

Asked in:Amazon, Microsoft, Facebook

#### Understanding the Problem

**Problem Description: **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 it as a linked list.

**For Example:**

Input: (1 -> 8-> 2) + (3 -> 6 -> 5)

Output: (4-> 4-> 8)

Explanation: 281+ 563= 844.

Input: (4 -> 8-> 1) + (3 -> 6 )

Output: 7-> 4-> 2

Explanation: 184+ 63= 247

The node structure for the Linked List passed to your function will be

```
class Node {
int val
Node *next
Node(int v)
{
val = v
next = NULL
}
}
```

**Possible follow-up questions to ask the interviewer:-**

- Is it possible that both linked lists are of different sizes? (
**Ans**: Yes) - Is there any, possibility that there can be leading zeros in linked lists? (
**Ans:**You may assume the two numbers do not contain any leading zero, except the number 0 itself.)

#### Solution

How do we add two numbers in real life? First, we add the digits at a unit place in both numbers and if it is greater than 10, we take a carry as 1 and place the unit digit of the sum in the unit place of the answer. We continue this process for the remaining places.

Solution idea

We will do the same if the numbers are in the form of a linked list. The idea is to traverse both linked lists and pick the nodes of both lists one by one and add them. We need to implement the concept of **carrying** too in our code.

We need to consider some cases that can happen during the iteration

- Size of linked lists are different - There will be a time in the iteration where there will not be further nodes left in one linked list, then we will just run through the other and maintain the carry if possible.
- An extra node is required for storing the final carry in output - Let us suppose we have an example for adding (9->9) + (1->1). The output will be 0->1->1. So there can be a possibility that one extra node is required for the output.

Solution Steps

- Initialize
**head**and**curr**to NULL which will store the head and the current node of the output list respectively. - Initialize
**carry**to 0. - Iterate the linked list till one reaches the end.

- Add the values of the nodes with
**carry**. - Generate
**carry**and find the unit place of sum. - Now if the
**head**is NULL, add the first node in the output linked list and also assign**curr = head**. - If
**head**is not NULL, then append new node in**curr**.**next**and make curr pointing to new node ie**curr = curr.next.**

4. Now, there might be a case that one linked list is not fully iterated so, again iterate through that list and add **carry** and node's value and generate **sum** and append this new node of the **sum** to **curr.next** and move **curr** to new node.

5. There might be a condition that both linked list are fully iterated but there is **carry** generated, so append this **carry** at the end of linked list

6. Return **head.**

Pseudo-Code

```
Node addTwoNumberInLists(Node A, Node B)
{
Node head = NULL, curr = NULL
int carry = 0
while( (A!= NULL) && (B!= NULL) )
{
int s = A.val + B.val + carry
carry = s / 10 // Ten's place, becomes 0 if s < 10
s = s % 10 // Unit's place
if( head == NULL )
{
head = Node(s)
curr = head
}
else
{
curr.next = Node(s)
curr = curr.next
}
A = A.next
B = B.next
}
while ( A != NULL )
{
int s = A.val + carry
carry = s / 10
s = s % 10
curr.next = Node(s)
curr = curr.next
A = A.next
}
while( B != NULL )
{
int s = B.val + carry
carry = s / 10
s = s % 10
curr.next = Node(s)
curr = curr.next
B = B.next
}
if( carry != 0 )
curr.next = Node(carry)
return head
}
```

Complexity Analysis

Time Complexity: O(M+N), where M and N are the lengths of two linked lists.

Space Complexity: O(1)

Critical ideas to think!

- Try solving this problem using recursion.
- How would you solve this question if the head is pointed to the most significant digit?

#### Suggested problems to solve

- Add 1 to a number represented as a linked list.
- Subtract two numbers represented as linked lists.
- Compare two strings represented as linked lists
- Multiply two numbers represented by linked lists.

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**May the code be with You! **

**Enjoy Algorithms!**