## Add Two Numbers as Lists

Difficulty: Medium

#### 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
1. Initialize head and curr to NULL which will store the head and the current node of the output list respectively.
2. Initialize carry to 0.
3. 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.
• 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

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

{
}
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)

}``````

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?