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:
Time complexity for above process is O(max(len(N1,N2))
C++ Implementation:
Output