Divij Sehgal Divij Sehgal - 8 days ago 19
C Question

Can't add two numbers using Linked Lists

I am trying to add two numbers stored as a linked list.

In the code below, the pointers to the first digit of each number are passed to the method addListNumbers() method. This calls the addNumbers() method to add k least significant bits of each number and addRemaining() method to add the remaining digits of the larger number.

#include <stdio.h>
#include <stdlib.h>

struct Node{
int data;
struct Node *next;
};

struct Node* addNode(struct Node* head, int data){
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->data=data;
if(head!=NULL)
head->next=node;
node->next=NULL;
return node;
}

void addRemaining(struct Node *num1, struct Node **result, int *carry, int diff){
int sum=0;
if(!num1||diff==0)
return;
addRemaining(num1->next, result, carry, diff-1);
sum=num1->data+*carry;
*carry=sum/10;
sum=sum%10;
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=sum;
temp->next=*result;
*result=temp;
return;
}

void addNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
int sum;
if(!num1)
return;
addNumbers(num1->next, num2->next,result,carry);
struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
// printf("sum=num1->data+num2->data+(*carry)----- %d",*carry);
sum=num1->data+num2->data+(*carry);
// printf("sum is:%d ",sum);
*carry=sum/10;
// printf("carry is:%d ",*carry);
sum=sum%10;
temp->data=sum;
temp->next=*result;
*result=temp;
return;
}

void addListNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
int l1Length=0, l2Length=0, diff=0;
struct Node *current=num1;
while(current!=NULL){
current=current->next;
l1Length++;
}
current=num2;
while(current!=NULL){
current=current->next;
l2Length++;
}
if(l1Length<l2Length){
current=num1;
num1=num2;
num2=current;
}
diff=abs(l1Length-l2Length);
current=num1;
while(diff){
current=current->next;
diff--;
}
addNumbers(current, num2, result, carry);
diff=abs(l1Length-l2Length);
addRemaining(num1, result, carry, diff);
// if(*carry){
// struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
// temp->next=*result;
// temp->data=temp->data+*carry;
// *result = temp;
// }
}

void printList(struct Node* list){
struct Node *current=(struct Node *)malloc(sizeof(struct Node));
current=list;
if(current==NULL)
return;
printf("%d", current->data);
printList(current->next);
}

int main(){
struct Node *num1 = addNode(NULL,6);
struct Node *n2 = addNode(num1,2);
struct Node *n3 = addNode(n2,7);
// struct Node *n4 = addNode(n3,4);
// struct Node *n5 = addNode(n4,5);
printf("Num 1:: ");
printList(num1);
printf("\n");
struct Node *num2 = addNode(NULL,8);
struct Node *n22 = addNode(num2,1);
struct Node *n23 = addNode(n22,6);
struct Node *n24 = addNode(n23,4);
struct Node *n25 = addNode(n24,7);
printf("Num 2:: ");
printList(num2);
printf("\n");
struct Node *result=(struct Node*)malloc(sizeof(struct Node));
int carry=0;
addListNumbers(num1, num2, &result, &carry);
printf("After Adding:");
printList(result);
printf("\n");
return 0;
}


The two numbers add up fine but the result also has an zero at the end. For the two numbers added above, it yields the following output:

Num 1:: 627
Num 2:: 81647
After Adding:822740


whereas the actual answer is 82274.

Any help is appreciated :)

Answer

Your function addNumbers recursively calculates the sum of 2 digits and puts the result in front of the list that is accessed via result parameter. Before you call addListNumbers you already prepare a initial last digit for your resulting list by allocating memory for the first node:

struct Node *result=(struct Node*)malloc(sizeof(struct Node));
...
addListNumbers(num1, num2, &result, &carry);

You fail to set result->next = NULL, but by accident the node you allocated is filled with zeros. This prevents you from getting SEGFAULT etc. In general you should initialize the memory you allocated properly. But in this case you should not allocate anything at all and set result to NULL instead.

BTW: In printList you allocate memory for a copy of your linked list. Afterwards this is not used any more and causes a memory leak. There is no need to allocate anything in that function. Just use list instead of current.

Comments