Problem
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list.
Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
Solution
#include <iostream>
using namespace std;
typedef struct linked_list{
int data;
struct linked_list *next;
}Linked_list;
int list_add(Linked_list **head, int d)
{
Linked_list *l = new Linked_list;
l->data = d;
l->next = NULL;
Linked_list *t = *head;
if(*head == NULL){
*head = l;
return 1;
}
while(t->next != NULL){
t = t->next;
}
t->next = l;
return 1;
}
void addlist(Linked_list **r, Linked_list *l1, Linked_list *l2)
{
Linked_list *t1 = l1;
Linked_list *t2 = l2;
Linked_list *t;
int len1 = 0, len2 = 0;
int carry = 0;
if(l1 == NULL && l2 == NULL){
*r = NULL;
return;
}
while(t1){
t1 = t1->next;
len1 ++;
}
while(t2){
t2 = t2->next;
len2 ++;
}
*r = (len1 > len2) ? l1 : l2;
t = *r;
while(l1 != NULL && l2 != NULL){
if(l1->data + l2->data + carry> 9){
t->data = l1->data + l2->data + carry - 10;
carry = 1;
}
else{
t->data = l1->data + l2->data + carry;
carry = 0;
}
t = t->next;
l1 = l1->next;
l2 = l2->next;
}
if(l1 == NULL){
while(l2 != NULL){
if(l2->data + carry > 9){
l2->data = l2->data + carry - 10;
carry = 1;
}
else{
l2->data = l2->data + carry;
carry = 0;
}
if(l2->next == NULL){
if(carry > 0){
t = new Linked_list;
t->data = carry;
t->next = NULL;
l2->next = t;
break;
}
}
l2 = l2->next;
}
}
else{
while(l1 != NULL){
if(l1->data + carry > 9){
l1->data = l1->data + carry - 10;
carry = 1;
}
else{
l1->data = l1->data + carry;
carry = 0;
}
if(l1->next == NULL){
if(carry > 0){
t = new Linked_list;
t->data = carry;
t->next = NULL;
l1->next = t;
break;
}
}
l1 = l1->next;
}
}
}
void delete_list(Linked_list *head)
{
while(head != NULL){
Linked_list *t = head->next;
delete head;
head = t;
}
}
void print_list(Linked_list *head)
{
while(head != NULL){
cout << head->data << " ";
head = head->next;
}
}
int main(int argc, char* argv[])
{
Linked_list *head1 = NULL;
Linked_list *head = NULL;
Linked_list *r = NULL;
list_add(&head, 1);
list_add(&head, 1);
list_add(&head, 2);
list_add(&head, 5);
list_add(&head1, 3);
list_add(&head1, 9);
list_add(&head1, 4);
list_add(&head1, 9);
list_add(&head1, 9);
cout << "List 1 ( ";
print_list(head);
cout << " )" << endl;
cout << "list 2 ( ";
print_list(head1);
cout << " )" << endl;
addlist(&r, head, head1);
cout << "result ( " ;
print_list(r);
cout << " )" << endl;
delete_list(head);
delete_list(head1);
return 0;
}
Output
list 1 ( 1 1 2 5 )
list 2 ( 3 9 4 9 9 )
result ( 4 0 7 4 0 1 )