Adding two numbers using linked lists

Question

I am trying to add two numbers that are represented by linked lists. So I have inserted the numbers 3->2->8 and 6->5->4. I have tried to get the numbers 328 and 654 and then added the two and insert them in a third list. I am facing some problems while calculating the number. Here is the code.

    #include<bits/stdc++.h>

using namespace std;


struct Node{
int data;
struct Node *next;
};
int flag=1;
void input(Node **head,int num)
{
    Node *temp=(struct Node*)malloc(sizeof(struct Node));
    temp->data=num;
    if(!flag)temp->next=*head;
    if(flag){temp->next=NULL;flag=0;}
    *head=temp;
}

void add(Node *l1,Node *l2,Node *l3)
{
    Node *cur1=l1;
    Node *cur2=l2;
    int size1=0,size2=0;

    while(cur1!=NULL)
    {
       size1++;

        cur1=cur1->next;
    }
    while(cur2!=NULL)
    {
        size2++;
        cur2=cur2->next;
    }
    int i=size1-1,j=size2-1,sum1=0,sum2=0;
    cur1=l1;cur2=l2;
    cout<<i<<endl;
    while(cur1!=NULL)
    {
        cout<<cur1->data<<"\t";
        cout<<cur1->data*pow(10,i)<<"\t";

        sum1=sum1+cur1->data*pow(10,i);
        cout<<sum1<<endl;
        i--;
        cur1=cur1->next;
    }
    cout<<sum1<<endl;
    while(cur2!=NULL)
    {    cout<<cur2->data<<"\t";
        cout<<cur2->data*pow(10,j)<<"\t";
        sum2=sum2+cur2->data*pow(10,j);
        cout<<sum2<<endl;
        j--;
        cur2=cur2->next;
    }
    cout<<sum2<<endl;
    sum1+=sum2;
    while(sum1!=0)
    {
        int r=sum1%10;
        input(&l3,r);
        sum1/=10;
    }
    cur1=l3;
    while(cur1!=NULL)
    {
        cout<<cur1->data;
        cur1=cur1->next;
    }
}

int main()
{
    Node *l1=NULL;
    Node *l2=NULL;
    Node *l3=NULL;
    input(&l1,8);
    input(&l1,2);
    input(&l1,3);
    flag=1;
    input(&l2,4);
    input(&l2,5);
    input(&l2,6);
    add(l1,l2,l3);
    return 0;
}

I get the output

2 //value of i
3       300     299 //cur1->data*pow(10,i) is initially 300 then becomes 299
2       20      319
8       8       327
327 //total sum which should be 328
6       600     599 //Same problem 
5       50      649
4       4       653
653 //total sum which should be 654
980 //sum of 327 and 653 

Answer 1

The code is a bit difficult to follow. You could simply sum the (simply) linked lists instead of extracting the values of each list, add them, and then store the result.

Below a simple example. Note that carry must be passed as reference, so the caller has access to the modified value when unwinding the stack. Also, this example assumes both lists have the same number of nodes. If not, you could add 0's to the shortest list.

// basic node structure
template <typename T>
struct Node
{
    T data = 0;
    Node<T>* next = nullptr;
};

// function to sum 2 simply linked lists
Node<int>* sumLists(Node<int>* l1, Node<int>* l2, int& carry, int k = -1)
{
    if (!l1 && !l2)
    {
        // we reached the end of both lists
        return nullptr;
    }

    ++k; // index of the largest list

    // iterate to the end of both lists, head is the head of the result list
    auto head = sumLists(l1 ? l1->next : l1, l2 ? l2->next : l2, carry, k);

    // compute the value and carry
    int value = carry;
    if (l1) value += l1->data;
    if (l2) value += l2->data;
    carry = value / 10;

    // insert the value into the result list
    Node<int>* node = new Node<int>();
    node->data = value % 10;
    if (!head)
    {
        head = node;
    }
    else
    {
        node->next =head;
        head = node;
    }

    // add carry for the last iteration
    if ((k == 0) && (carry != 0))
    {
        Node<int>* node = new Node<int>();
        node->data = carry;
        node->next = head;
        head = node;
    }

    return head;
}

Answer 2

The problem may be due to truncation. The pow function returns floating point. Then you convert it to integer which causes a truncation.

Example:

299.99999999 as float will become 299 as int

Try to add 0.5 first to get rounding instead.

Like:

sum1=sum1+(cur1->data*pow(10,i) + 0.5);

As commented by @viraptor it is even better to avoid float (i.e. pow). Try something like:

sum1 = 0;
while(cur1 != NULL)
{
    sum1 = 10 * sum1;
    sum1 = sum1 + cur1->data;
    cur1=cur1->next;
}

then all calculations are done on integers and you will not get problems due to conversion between float and int.