# Recursive, O(1) space, simple C++ solution

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

int length1 = length(l1);
int length2 = length(l2);

ListNode *res;
int carry = 0;
if (length1 >= length2)
{
res = l1;
}
else
{
res = l2;
}

if (carry)
{
ListNode *tmp = new ListNode(1);
tmp->next = res;
res = tmp;
}

return res;
}

int add(ListNode *bigger, ListNode *smaller, int diff)
{
if (bigger == NULL)
{
return 0;
}

int carry, num;
if (diff > 0)
{
num = carry + bigger->val;
}
else
{
num = carry + bigger->val + smaller->val;
}

bigger->val = num % 10;

return num / 10;
}

// Calculates length
int length(ListNode* l1)
{
return (l1 == NULL) ? 0 : length(l1->next)+1;
}
};
``````

• For future reference, a recursive solution cannot be O(1) because each call takes up room on the stack

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.