Sum of two numbers represented by linked lists
Given two numbers represented by two linked lists of size N1 and N2. The task is to return a sum list. The sum list, which is a linked list representation of the addition of two input numbers.
Input:
The first line of input contains the number of test cases T. For each test case, the first line of input contains the length of the first linked list and the next line contains N1 elements of the linked list. Again, the next line contains N2, and the following line contains M elements of the linked list.
Output:
Output the resultant linked list representing the sum of given two linked list.
Example with explanation:
Input:
T = 1
N1 = 3
[1->5->4]
N2 = 3
[2->3->5]
Output:
[3->8->9], as 451+532 = 983
Input:
T = 1
N1 = 3
[2->4->3]
N2 = 3
[5->6->4]
Output:
[7->0->8], as 342+465 = 807
We will use the same way of addition as we use to do during elementary school, we will keep track of carry using a variable car and traverse digit by digit sum starting from the head of two linked list which contains least significant digit to most significant digits.
Pseudo Code:
Node sum(Node a,Node b){ //Let Temp1 and temp2 be some Nodes int carry=0 // initilise carry as 0 // temp2 is used as dummy for adding new node and // temp1 will be use as the header for the // sum value linked list temp2=temp1 int x,y //used for storing nodes values while(a!=NULL or b!=NULL) { if(a!=NULL) {x=a->data,a=a->next;} else x=0 if(b!=NULL) {y=b->data,b=b->next;} else y=0 int sum=x+y+carry temp2->next=new Node(sum%10) // store the digit(0-9) carry=sum/10 // sum/10 gives carry temp2=temp2->next } if(carry!=0) // if carry is not zero then add it at last. temp2->next=new Node(carry) return temp1->next // return the new Node head }Time complexity for above process is O(max(len(N1,N2))
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer