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:
Code:
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:
- Have pointer on each head of the two list
- Add the data of two nodes along with carry.
- create new result node and put the value, SUM % 10
- assign SUM / 10 to carry
- Repeat until any one list exhausts.
- Then add the carry to the node, repeat till end of list
Code:
Your solution is good, I have also written a similar solution. Here is the code in c from <a href='http://k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html>http://k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html</a>:
ReplyDeletenode *long_add(mynode *h1, mynode *h2, mynode *h3) //h3 = h2+h1
{
node *c, *c1, *c2;
int sum, carry, digit;
carry = 0;
c1 = h1->next;
c2 = h2->next;
while(c1 != h1 && c2 != h2)
{
sum = c1->value + c2->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c1 = c1->next;
c2 = c2->next;
}
if(c1 != h1)
{
c = c1;
h = h1;
}
else
{
c = c2;
h = h2;
}
while(c != h)
{
sum = c->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c = c->next;
}
if(carry==1)
{
h3 = insertNode(carry, h3);
}
return(h3);
}