Input: [ 3 -> 4 -> 5 ] + [ 1 -> 2-> 3]
Output: [ 8 -> 6 -> 4 ]
Explanation: 543 + 321 = 8 -> 6 -> 4
Detailed Explanation:
Let’s take a simple example on how we add on a paper:
199
+ 1
=====
200
Pictorial representation:
Here we have to take the least significant digit and add it. If the resultant digit is 10 [overflow], then we carry 1. That carry is added to the next digit and solved until it reaches the most significant digit.
In our solution, we use the same logic. Below are the steps that we shall be performing:
Step 1: Take a head pointer to both of the lists. Take “result_list” linked list to store the sum.
Step 2: Initialize “sum” and “carry” variables.
Sum variable will keep track of the total sum.
Carry variable will check if there is an overflow.
Step 3: Add the first number of list 1 to the first number of list 2.
Calculate if the sum is greater than 10, then update the carry for next calculation.
If the sum is greater than 10, then get the current sum by using “sum = sum % 10” formula.
Step 4: Update the sum in “result _list” linked list.
Step 5: Go to the next node.
In case, if one node has more nodes than the other, then other list remaining value will be filled by 0.
Solution in C
#include<stdio.h> #include<stdlib.h> /* create a linked list*/ struct Node { int data; struct Node *next; }; /* Create a new node */ struct Node* newNode(int value) { struct Node *newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->data = value; newNode->next = NULL; return newNode; } /*Insert a new node at the begenning*/ void insert_node(struct Node** head_ref, int new_data) { /* create new 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; } /* Print linked list */ void displayList(struct Node *node) { while(node != NULL) { printf("%d ", node->data); node = node->next; } printf("\n"); } /* Add two list number*/ struct Node* addTwoValues(struct Node *first_list, struct Node *second_list) { struct Node *result_list = NULL; // Holds the final list struct Node *temp = NULL; // To create new node for result struct Node *prev = NULL; int sum = 0; // To hold sum int carry = 0; // to update carry, if present while (first_list != NULL || second_list != NULL) { sum = carry + (first_list? first_list->data: 0) + (second_list? second_list->data: 0); // if carry is present, then update it for next calculation in next iteration. carry = (sum >= 10)? 1 : 0; // update the sum, if it is greater than 10 sum = sum % 10; // create a node to update the sum. temp = newNode(sum); if(result_list == NULL) result_list = temp; else prev->next = temp; prev = temp; if (first_list) first_list = first_list->next; if (second_list) second_list = second_list->next; } if (carry > 0) temp->next = newNode(carry); return result_list; } int main(void) { struct Node* res_list = NULL; struct Node* first_list = NULL; struct Node* second_list = NULL; // create first list 3->4->5 insert_node(&first_list, 3); insert_node(&first_list, 4); insert_node(&first_list, 5); printf("First Linked List is "); displayList(first_list); // create second list 1->2->3 insert_node(&second_list, 1); insert_node(&second_list, 2); insert_node(&second_list, 3); printf("second_list List is "); displayList(second_list); // Add the two lists and see result res_list = addTwoValues(first_list, second_list); printf("Result list is "); displayList(res_list); return 0; }
Agnibha Chakraborty
#include
#define NULL 0
using namespace std;
struct Node{
int data;
Node *next;
Node *prev;
};
Node * Insert(Node *head, int data){
Node *temp = new Node();
temp->data = data;
temp->next = NULL;
temp->prev = NULL;
if(head == NULL){
head = temp;
// cout << head<<endl;
// cout<<"Inserted!"<<endl;
}
else{
// cout<<"Inserted!2"<next = head;
head = temp;
temp->next->prev = temp;
}
return head;
}
void Print(Node *head){
Node *temp = head;
while(temp !=NULL){
cout<data<next;
}
cout <next;
// head->next = prev;
// prev = head;
// head = next;
// }
// return prev;
//}
Node * Reverse2(Node * head){
Node *temp = NULL,*current;
while(head != NULL){
current = head;
temp = head->next;
head->next = head->prev;
head->prev = temp;
head = temp;
}
return current;
}
Node * add(Node *head1, Node *head2, Node *head3){
Node *current1, *current2;
int sum=0, carry=0;
while(head1!=NULL){
current1 = head1;
head1=head1->next;
}
while(head2!=NULL){
current2 = head2;
head2=head2->next;
}
while(current1 != NULL || current2 != NULL){
sum = carry + (current1->data>0?current1->data:0) + (current2->data>0?current2->data:0);
carry = sum>9? 1 : 0;
sum%=10;
head3 = Insert(head3,sum);
if(current1 !=NULL) current1 = current1->prev;
if(current2 !=NULL) current2 = current2->prev;
}
if (carry>0) head3 = Insert(head3,1);
return head3;
}
int main(){
Node *first_head = NULL;
Node *second_head = NULL;
Node *result_head = NULL;
first_head = Insert(first_head,2);
first_head =Insert(first_head,4);
first_head =Insert(first_head,3);
cout << "Content of the First List: ";
Print(first_head);
second_head = Insert(second_head,5);
second_head = Insert(second_head,6);
second_head = Insert(second_head,4);
cout <<"Content of the Second List: ";
Print(second_head);
cout<<endl<“<<endl<<endl;
first_head = Reverse2(first_head);
cout <<"Content of the First List: ";
Print(first_head);
second_head = Reverse2(second_head);
cout <<"Content of the Second List: ";
Print(second_head);
result_head = add(first_head,second_head,result_head);
cout <<endl<<"Content of the Result List: ";
Print(result_head);
return 0;
}
Agnibha Chakraborty
/*Day 2 Question:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Difficulty: Medium
Asked in company: Amazon */
Brayan
Can anyone provide java code for these solutions, please