Difficulty Level Medium

Add two numbers is a problem in which we have given two non-empty linked list representing a non-negative integer. The digit are store in reverse order and every node must contain only a single digit. Add the two numbers and print the result by using a linked list.

## Input Format

First-line containing two integer values N1 and N2. Second-line containing N1 digits of the first number. Third line containing N2 digits of the number.

## Output Format

Print the result by use of a linked list.

## Constraints

• 0<=node value<=9.
```Example Input-1:
3 3
5 2 1
2 8 5```
```Example Output-1:
7 0 7```

## Explanation For Add two numbers

The first number is 125 and the second number is 582. On adding them we got 707. So, our final answer is 707. For better understanding see the below images:

Step:1 Create the linked lists as per the given input format. Add the digits in a linked list in reverse order.

Step:2  Traverse from right to left one by one digit in each linked list. We reverse these linked lists for traversing right to left. Add the data of the nodes of both linked list and store it in another linked list. If there is any carry occurs between the addition then use it in the next node.

Step:5 Now, we print the values of the resultant linked list 7->0->7.

## Algorithm For Add two numbers

```Algorithm:
while(h1!=NULL and h2!=NULL) then:
Step:2 while(h1!=NULL) then:
Step:3 while(h2!=NULL) then:
Step:4 Print the final resultant linked list.```

## Implementation For Add two numbers

```/*C++ Implementation of Add two numbers problem*/
#include<bits/stdc++.h>
using namespace std;
/*structure of node of linked list which contain data and a pointer which is point to the next node*/
struct ListNode
{
/*value of node*/
int val;
/*pointer to the next node*/
ListNode *next;
};
/*Create a node with given data*/
ListNode *newnode(int data)
{
ListNode *temp= new ListNode();
temp->val=data;
temp->next=NULL;
return temp;
}
{
/*allocate node*/
ListNode* temp = newnode(data);
/*link the old list off the new node*/
/* move the head to point to the new node*/
}
{
{
}
}
{
int carry=0;
ListNode* res;
ListNode **ans=&res;
/*if both linked list have nodes*/
while(l1!=NULL&&l2!=NULL)
{
(*ans)= newnode((l1->val+l2->val+carry)%10);
carry=(l1->val+l2->val+carry)/10;
ans=&((*ans)->next);
l1=l1->next;
l2=l2->next;
}
/*if linked list 1 have nodes*/
while(l1!=NULL)
{
(*ans)= newnode((l1->val+carry)%10);
carry=(l1->val+carry)/10;
ans=&((*ans)->next);
l1=l1->next;
}
/*if linked list 2 have nodes*/
while(l2!=NULL)
{
(*ans)= newnode((l2->val+carry)%10);
carry=(l2->val+carry)/10;
ans=&((*ans)->next);
l2=l2->next;
}
/*if their is generate a carry then create one more node in linked list and store the carry.*/
if(carry>0)
{
(*ans)= newnode(carry);
carry/=10;
ans=&((*ans)->next);
}
return res;
}
/*function use to reverse the linked list*/
{
ListNode* next=NULL;
ListNode* prev=NULL;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
return prev;
}
int main()
{
int n1,n2;
/*take the input n1,n2*/
cin>>n1>>n2;
ListNode* result=NULL;
ListNode* ll1=NULL;
ListNode* ll2=NULL;
for(int i=0;i<n1;i++)
{
int x;
cin>>x;
}
for(int i=0;i<n2;i++)
{
int x;
cin>>x;
}
cout<<endl;
cout<<endl;
cout<<endl;
return 0;
}```
```3 2
2 4 3
5 6```
```First linked list is: 3 4 2
Second linked list is: 6 5
Resultant linked list is: 7 0 4```

## Time Complexity

O(N) where N is the maximum value of n1,n2. We just traverse the linked list in linear time so the time complexity is also linear.

## Space Complexity

O(N) because we create another linked list which may contain N nodes where N is the digit in the big size linked list.

References

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek was able to crack Microsoft after practicing questions from TutorialCup