# Recursive C++ solution with O(n) time and space complexity where n is max(length(A),length(B))

/**

• struct ListNode {
• ``````int val;
``````
• ``````ListNode *next;
``````
• ``````ListNode(int x) : val(x), next(NULL) {}
``````
• };
*/

ListNode* helper(ListNode* A, ListNode* B,int carry){
if(A==NULL&&B==NULL){
if(carry>0){
ListNode* newNode = new ListNode(carry);
return newNode;
}
else return NULL;
}
if(A==NULL&&B!=NULL){
if(carry==0){
return B;
}
else{
ListNode* newNode1 = new ListNode((carry + B->val)%10);
carry = (carry + B->val)/10;
newNode1->next = helper(NULL,B->next,carry);
return newNode1;
}
}
if(B==NULL&&A!=NULL){
if(carry==0){
return A;
}
else{
ListNode* newNode2 = new ListNode((carry + A->val)%10);
carry = (carry + A->val)/10;
newNode2->next = helper(NULL,A->next,carry);
return newNode2;
}
}
// BASE CASE

``````int ncar = carry + A->val + B->val; //new carry
carry = ncar/10;
ncar = ncar%10;

ListNode* temp3 = new ListNode(ncar);
temp3->next =  helper(B->next,A->next,carry);
return temp3;
``````

}
ListNode* Solution::addTwoNumbers(ListNode* A, ListNode* B) {
if(A==NULL&&B==NULL){
return NULL;
}
if(A==NULL&&B!=NULL){
return B;
}
if(A!=NULL&&B==NULL){
return A;
}
int carry = 0;
carry = (A->val+B->val)/10;
ListNode* t = new ListNode(0);
t->val = (A->val+B->val)%10;
t->next= helper(A->next,B->next,carry);

return t;
}