Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers.
Algo:
// https://www.geeksforgeeks.org/add-two-numbers-represented-by-linked-lists/
#include <iostream>
#include <list>
using namespace std;
struct linked_list {
int data;
struct linked_list *next;
};
typedef struct linked_list node;
void print (node* n) {
while (n) {
cout<< n->data;
n = n->next;
}
return;
}
void insert (node **headref, int n) {
node* head = *headref;
node *temp = new node;
temp->data = n;
temp->next = NULL;
if (head == NULL) {
*headref = temp;
return;
}
while (head->next)
head = head->next;
head->next = temp;
return;
}
void push(node** headref, int n) {
node* temp = new node;
temp->data = n;
temp->next = *headref;
*headref = temp;
}
node* ReverseList (node* head) {
node* next = NULL, *current = head, *prev = NULL;
while (current) {
next = current->next;
current->next = prev;
prev=current;
current = next;
}
return prev;
}
node* add(node** head1ref, node** head2ref) {
node* head1 = *head1ref;
node* head2 = *head2ref;
node* head = NULL;
head1 = ReverseList(head1);
head2 = ReverseList(head2);
int sum, carry = 0;
while (head1 || head2) {
sum = carry + (head1?head1->data:0) + (head2?head2->data:0);
carry = (sum>9)?1:0;
sum = sum%10;
push(&head, sum);
if (head1)
head1 = head1->next;
if (head2)
head2 = head2->next;
}
if (carry>0)
push(&head, carry);
return head;
}
int main() {
int n;
node* head1 = NULL, *head2 = NULL;
cout<< "Enter the first number\n";
while (true) {
cout<< "Enter the digit: ";
cin>>n;
if (n==-9)
break;
else
insert(&head1, n);
}
cout<< "Enter the second number\n";
while (true) {
cout<< "Enter the digit: ";
cin>>n;
if (n==-9)
break;
else
insert(&head2, n);
}
cout<< "First number is: ";
print(head1);
cout<< "\nSecond number is: ";
print(head2);
node* head=add(&head1, &head2);
cout<< "\nSum of the numbers is: ";
print(head);
}