/* From Cracking the Coding Interview 2-4 */
/* 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. */
node * sumAsListNodes(node * n1, node * n2) {
if (n1 == nullptr && n2
== nullptr) {
return nullptr;
}
node * p1 = n1; node *
p2 = n2;
node * sum = new node();
node * head = sum;
int carry = 0; int digit;
while (p1 != nullptr && p2
!= nullptr) {
int s =
p1->value + p2->value + carry;
if (s >= 10) {
carry = 1;
digit = s - 10;
} else {
carry = 0;
digit = s;
}
node * n = new node(digit);
sum->next = n;
sum = sum->next;
p1 = p1->next; p2
= p2->next;
}
node * p = (p1 != nullptr? p1 : p2);
while (p != nullptr || carry == 1) {
int s = (p == nullptr? carry :
p->value + carry);
if (s >= 10) {
carry = 1;
digit = s - 10;
} else {
carry = 0;
digit = s;
}
node * n = new node(digit);
sum->next = n;
sum = sum->next;
if (p != nullptr) {
p = p->next;
}
}
sum = head;
sum = sum->next;
delete head;
return sum;
}
Liked your solution in c, mine is also based on same idea. 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);
}