Q:

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
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:

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node //declare Node
{
Node* next;
int data;
Node(int data)
{
this->data = data; // node value
this->next = NULL; // node pointer
}
};

{
// declare two nodes temp and p
Node *temp, *p;
// createNode will return a new node with
// data = value and next pointing to NULL.
temp = new Node(value);
}
else {
while (p->next != NULL) {
// traverse the list until p is the last node.
// The last node always points to NULL.
p = p->next;
}
// Point the previous last node to the
// new node created.
p->next = temp;
}
}

Node* sum(Node* a, Node* b)
{
Node *temp1, *temp2; // initilise two Nodes
temp1 = new Node(0);
temp2 = temp1;
int x, y;
int carry = 0; // initially carry is zero
while (a != NULL or b != NULL) {
// if node a is NOT NULL then x=a->data
if (a != NULL) {
x = a->data;
a = a->next;
}
else
x = 0;
if (b != NULL) {
// if node a is NOT NULL then x=a->data
y = b->data;
b = b->next;
}
else
y = 0;
int sum1 = x + y + carry;
temp2->next = new Node(sum1 % 10);
carry = sum1 / 10;
temp2 = temp2->next;
}
if (carry) // if carry is not zero
temp2->next = new Node(carry);
// list after summation.
return temp1->next;
}

// function to print linked list
{
else
}
}

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
cout << "Enter size of node N1: ";
ll n1, n2;
cin >> n1;

Node *a, *b;
ll x;

cout << "Enter its elements: ";
for (ll i = 0; i < n1; i++) {
cin >> x;
if (i == 0) {
a = new Node(x);
}
else
}

cout << "Enter size of node N2: ";
cin >> n2;

cout << "Enter its elements: ";
for (ll i = 0; i < n2; i++) {
cin >> x;
if (i == 0) {
b = new Node(x);
}
else
}

cout << "The final sum is: ";
print(sum(a, b));
cout << "\n";
}
return 0;
}
``````

Output

```Enter number of test cases: 3
Enter size of node N1: 3
Enter its elements: 2 3 4
Enter size of node N2: 3
Enter its elements: 8 1 7
The final sum is: 0->5->1->1
Enter size of node N1: 3
Enter its elements: 2 1 3
Enter size of node N2: 4
Enter its elements: 1 2 3 4
The final sum is: 3->3->6->4
Enter size of node N1: 2
Enter its elements: 1 2
Enter size of node N2: 2
Enter its elements: 2 4
The final sum is: 3->6```