We are given two numbers stored in a Linked List in reverse order, where each node of the Linked List represents the digit in the given numbers such that value stored at the first node is the first digit of the number, we have to add the number and store the result again a Linked List in the reverse order
Ex: 6 -->5 -->4 -->3 => 3456 is the first number
9 -->8 -->7 => 789 is the second number
result => 5 -->4 -->2 -->4 (3456 + 987 = 4245)
Read more about Linked List here…
Algorithm
- First, we will convert the linked list into the original number. (Note: digits are stored in reverse order of the original number)
- Then, we will Sum both the numbers
- Finally, we will store the resulting sum digit again into the linked list format in reverse order.
int convert_list_to_num(Node* list){
int num=0, i=0;
while(list != NULL){
num = num + (pow(10,i)*(list->digit));
list = list->next;
i++;
}
return num;
}
Node* convert_sum_to_list(int sum){
Node *head,*prev;
while(num){
Node *temp = new Node();
temp->digit = num%10;
num = num/10;
temp->next = NULL;
if(prev == NULL){
prev = temp;
head = prev;
}
else{
prev->next = temp;
prev = prev->next;
}
return head;
}
Node* find_sum(Node *list1, Node *list2){
int sum = 0;
sum = convert_list_to_num(list1) + convert_list_to_num(list2);
Node *list3 = convert_sum_to_list(sum);
return list3;
}
CPP implementation of the above algorithm
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int digit;
Node *next;
};
int convert_list_to_num(Node* list){
int num=0, i=0;
while(list != NULL){
num = num + (pow(10,i)*(list->digit));
list = list->next;
i++;
}
return num;
}
Node* convert_sum_to_list(int sum){
Node *head=NULL,*prev=NULL;
while(sum){
Node *temp = new Node();
temp->digit = sum%10;
sum = sum/10;
temp->next = NULL;
if(prev == NULL){
prev = temp;
head = prev;
}
else{
prev->next = temp;
prev = prev->next;
}
}
return head;
}
Node* find_sum(Node *list1, Node *list2){
int sum = 0;
sum = convert_list_to_num(list1) + convert_list_to_num(list2);
Node *list3 = NULL;
list3 =convert_sum_to_list(sum);
return list3;
}
int main(){
Node *list1=NULL, *list2=NULL, *current=NULL;
//creating list1
for(int i=6;i>=3;i--){
Node *temp = new Node;
temp->digit = i;
temp->next = NULL;
if(list1==NULL){
current = temp;
list1 = current;
}
else{
current->next = temp;
current = current->next;
}
}
//printing list1
cout<<"List1: ";
current = list1;
while(current!=NULL){
cout<<current->digit<<"->";
current = current->next;
}
cout<<"NULL"<<endl;
//creating list2
current = NULL;
for(int i=9;i>=7;i--){
Node *temp = new Node;
temp->digit = i;
temp->next = NULL;
if(list2==NULL){
current = temp;
list2 = current;
}
else{
current->next = temp;
current = current->next;
}
}
//priting list 2
cout<<"List2: ";
current = list2;
while(current!=NULL){
cout<<current->digit<<"->";
current = current->next;
}
cout<<"NULL"<<endl;
Node *list3 =find_sum(list1, list2);
//printing list3
cout<<"list3: ";
while(list3!=NULL){
cout<<list3->digit<<"->";
list3 = list3->next;
}
cout<<"NULL"<<endl;
return 0;
}
Output
List1: 6->5->4->3->NULL
List2: 9->8->7->NULL
list3: 5->4->2->4->NULL
The time complexity of the above algorithm in O(A+B), where A is the size of the first list, and B is the size of the second list.
