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.