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.
Table of Contents
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:3 Move the heads next by one and add the value to the resultant linked list.
Step:4 Move the heads next by one and add the value to the resultant linked list.
Step:5 Now, we print the values of the resultant linked list 7->0->7.
Algorithm For Add two numbers
Algorithm:
Step:1 If h1 is the head of first linked list and h2 is the head of second linked list then:
while(h1!=NULL and h2!=NULL) then:
1.1) add the data of both nodes and add to a final resultant linked list.
Step:2 while(h1!=NULL) then:
add the nodes of linked list 1 to the resultant linked list.
Step:3 while(h2!=NULL) then:
add the nodes of linked list 2 to the resultant linked list.
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;
}
void create_linked_list(ListNode** head, int data)
{
/*allocate node*/
ListNode* temp = newnode(data);
/*link the old list off the new node*/
temp->next=(*head);
/* move the head to point to the new node*/
(*head)=temp;
}
void print_linked_list(ListNode* head)
{
while(head!=NULL)
{
cout<<head->val<<" ";
head=head->next;
}
}
/*add two linked list*/
ListNode* add_two_numbers(ListNode* l1, ListNode* l2)
{
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* reverse_linked_list(ListNode* head)
{
ListNode* current=head;
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;
/*take input linked list 1*/
for(int i=0;i<n1;i++)
{
int x;
cin>>x;
create_linked_list(&ll1,x);
}
/*take input linked list 2*/
for(int i=0;i<n2;i++)
{
int x;
cin>>x;
create_linked_list(&ll2,x);
}
/*print first linked list*/
cout<<"First linked list is: ";
print_linked_list(ll1);
cout<<endl;
/*print second linked list*/
cout<<"Second linked list is: ";
print_linked_list(ll2);
cout<<endl;
/*reverse linkel list 1*/
ListNode* l1=reverse_linked_list(ll1);
/*reverse linkel list 2*/
ListNode* l2=reverse_linked_list(ll2);
ListNode* ans= add_two_numbers(l1,l2);
/*print reslutant linked list*/
cout<<"Resultant linked list is: ";
print_linked_list(ans);
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.