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
Approach:
We can implement this recursively by adding node by node, just as we would digit by digit.
1. result.data = (node1 + node2 + any earlier carry) % 10
2. if node1 + node2 > 10, then carry a 1 to the next addition.
3. add the tails of the two nodes, passing along the carry.
Input/Output:
A = 8 -> 7 -> 1 -> 1 -> null
B = 6 -> 3 -> 4 -> null
Adding the above linked lists:
Result: 4 -> 1 -> 6 -> 1 -> null
Liked your code in java, Here is the code in c, though idea is same. 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>:
ReplyDelete<pre>
node *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);
}
</pre>
how it works plzz giv full implementation..
ReplyDelete#include
ReplyDelete#include
/* Linked list node */
struct Node {
int data;
struct Node* next;
};
/* Function to create a new node with given data */
struct Node* newNode(int data)
{
struct Node* new_node = (struct Node*)
malloc(
sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/* Function to insert a node
at the beginning of the Singly Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = newNode(new_data);
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Adds contents of two linked
lists and return the head node
of resultant list */
struct Node* addTwoLists(
struct Node* first,
struct Node* second)
{
// res is head node of the resultant list
struct Node* res = NULL;
struct Node *temp, *prev = NULL;
int carry = 0, sum;
// while both lists exist
while (first != NULL || second != NULL) {
// Calculate value of next
// digit in resultant list.
// The next digit is sum
// of following things
// (i) Carry
// (ii) Next digit of first
// list (if there is a next digit)
// (ii) Next digit of second
// list (if there is a next digit)
sum = carry + (first ? first->data : 0)
+ (second ? second->data : 0);
// Update carry for next calulation
carry = (sum >= 10) ? 1 : 0;
// Update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = newNode(sum);
// if this is the first node then
// set it as head of the resultant list
if (res == NULL)
res = temp;
// If this is not the first node
// then connect it to the rest.
else
prev->next = temp;
// Set prev for next insertion
prev = temp;
// Move first and second
// pointers to next nodes
if (first)
first = first->next;
if (second)
second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
// return head of the resultant list
return res;
}
// A utility function to print a linked list
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
/* Driver program to test above function */
int main(void)
{
struct Node* res = NULL;
struct Node* first = NULL;
struct Node* second = NULL;
// create first list 7->5->9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
// create second list 8->4
push(&second, 4);
push(&second, 8);
printf("Second List is ");
printList(second);
// Add the two lists and see result
res = addTwoLists(first, second);
printf("Resultant list is ");
printList(res);
return 0;
}