## Given two numbers which are represented by two lists, write a  funtion that will find the sum of two  numbers and prints the list which is the representation of the sum.

### Example

INPUT :
list1: 3->2->1 //Number is 123
list2: 2->4->5 //Number is 542

OUTPUT :
sum: 5->6->6 //Sum is 665

## Method 1 :

Time Complexity : O(m + n),

where m is the number of nodes in list1 and n is the number of nodes in list2.

## Algorithm

1. Traverse through both lists

2. Add the elements in both lists ie, sum =  carry + list1element + list2element.

3. If the sum is greater than or equal to 10, then create a new node with (sum-10) as data and insert it in the result list and make carry =1

4. If sum is less than 10, then just create a new node with sum as the data and insert it in the result list.

5. Return the result list

## C++ Program

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

struct LLNode{
int data;
LLNode *next;
};
//Creates a new node with given data
LLNode *newNode(int data)
{
LLNode *new_node = new LLNode;
new_node->data = data;
new_node->next = NULL;
return new_node;
}

LLNode* addTwoLists (LLNode* list1, LLNode* list2)
{
LLNode* result = NULL; // result is head node of the resultant list
LLNode *temp, *prev = NULL;
int carry = 0, sum;

while (list1 != NULL || list2 != NULL) //while both lists exist
{
//calculating the sum of both elements in list1 and list2
//If there there is no elment in any list, just only add element in other list
sum = carry + (list1? list1->data: 0) + (list2? list2->data: 0);

// update carry for next calulation
// update sum if it is greater than 10
if (sum>=10)
{
sum = sum - 10;
carry = 1;
}
else
carry =0;

// 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(result == NULL)
result = temp;
else // If this is not the first node then connect it to the rest.
prev->next = temp;

// Set prev for next insertion
prev  = temp;

// Move list1 and list2 pointers to next nodes
if (list1) list1 = list1->next;
if (list2) list2 = list2->next;
}

if (carry > 0)
temp->next = newNode(carry);

// return head of the resultant list
return result;
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{
LLNode *result = NULL;
LLNode *list1 = NULL; //initial list has no elements

insertAtBeginning(&list1,5);
insertAtBeginning(&list1,4);
insertAtBeginning(&list1,8);

LLNode *list2 = NULL;
insertAtBeginning(&list2,5);
insertAtBeginning(&list2,2);
insertAtBeginning(&list2,8);

cout<<"\n Two lists are :-\n";
cout<<"first number is 548"<<endl;
display(&list1);
cout<<"second number is 528"<<endl;
display(&list2);

cout<<"After adding two lists sum is 1076"<<endl;
display(&result);
return 0;
}``````

## Method 2 :

In the previous method, least significant digit is first node of lists and most significant digit is last node. In this problem, most significant node is first node and least significant digit is last node.

### In this method we will not use any extra space or modify lists. we use recursionExample

INPUT :
list1 : 3->2->1 //Number is 321
list2 : 2->4->5 //Number is 245

OUTPUT :
sum: 5->6->6//Sum is 566

Time Complexity: O(m + n),

## where m is the number of nodes in list1 and n is the number of nodes in list2Algorithm

1. Calculate the sizes of two lists

2. If sizes are same, then calculate sum using recursion. Hold all nodes in recursion call stack till the rightmost node, calculate sum of rightmost nodes and forward carry to left side.

3. If sizes are not same,

a) Calculate difference of sizes of two linked lists. Let the difference be diff

b) Move diff nodes ahead in the bigger linked list. Now use step 2 to calculate sum of     smaller list and right sub-list (of same size) of larger list. Also, store the carry of this sum.

c) Calculate sum of the carry (calculated in previous step) with the remaining left sub-list of     larger list. Nodes of this sum are added at the beginning of sum list obtained previous step.

## C++ Program

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

struct LLNode{
int data;
LLNode *next;
};
//Protype
//Swaping the two pointers
void swapPointer(LLNode** a, LLNode** b )
{
LLNode* temp = *a;
*a = *b;
*b = temp;
}

// function to get size of linked list //
int getSize(LLNode *list)
{
int size = 0;
while (list != NULL)
{
list = list->next;
size++;
}
return size;
}

// Adds two linked lists of same size represented by list1 and list2 and returns
// Carry is propagated while returning from the recursion
LLNode* ifSameSize(LLNode* list1, LLNode* list2, int* carry)
{
// Since the function assumes linked lists are of same size,
// check any of the two head pointers
if (list1 == NULL)
return NULL;

int sum;

// Allocate memory for result node of current two nodes
LLNode* result = new LLNode;

// Recursively add remaining nodes and get the carry
result->next = ifSameSize(list1->next, list2->next, carry);

// add digits of current nodes and propagated carry
sum = list1->data + list2->data + *carry;
*carry = sum / 10;
sum = sum % 10;

// Assign the sum to current node of resultant list
cout<<sum;
result->data = sum;

return result;
}

// After the smaller list is added to the bigger lists's sublist of same size.
//  the carry must be added to left side of larger list to get the final result.
void addCarryToRemaining(LLNode* list1, LLNode* cur, int* carry, LLNode** result)
{
int sum;

// If diff. number of nodes are not traversed, add carry
if (list1 != cur)
{

sum = list1->data + *carry;
*carry = sum / 10;
sum = sum % 10;

// add this node to the front of the result
insertAtBeginning(result, sum);
}
}

// The main function that adds two linked lists represented by list1 and list2.
// The sum of two lists is stored in a list referred by result
void addTwoLists(LLNode* list1, LLNode* list2, LLNode** result)
{
LLNode *cur;

// If first list is empty
if (list1 == NULL)
{
*result = list2;
return;
}

// If second list is empty
else if (list2 == NULL)
{
*result = list1;
return;
}

int size1 = getSize(list1);
int size2 = getSize(list2) ;

int carry = 0;

if (size1 == size2)
*result = ifSameSize(list1, list2, &carry);

else
{
int diff = abs(size1 - size2);

// First list should always be larger than second list.
// If not, swap pointers
if (size1 < size2)
swapPointer(&list1, &list2);

// move diff. number of nodes in first list
for (cur = list1; diff--; cur = cur->next);

// get addition of same size lists
*result = ifSameSize(cur, list2, &carry);

// get addition of remaining first list and carry
}

// if some carry is still there, add a new node to result
if (carry)
insertAtBeginning(result, carry);
}

{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{
LLNode *result = NULL;
LLNode *list1 = NULL; //initial list has no elements

insertAtBeginning(&list1,5);
insertAtBeginning(&list1,4);
insertAtBeginning(&list1,8);

LLNode *list2 = NULL;
insertAtBeginning(&list2,5);
insertAtBeginning(&list2,2);
insertAtBeginning(&list2,8);

cout<<"\n Two lists are :-\n";
cout<<"first number is 845"<<endl;
display(&list1);
cout<<"second number is 825"<<endl;
display(&list2);