# C solution: linear time and O(1) space except answer itself using recursion (45ms, non-recursive)

• /**

• struct ListNode {

• ``````int val;
``````
• ``````struct ListNode *next;
``````
• };
*/
int getListLength(const struct ListNode *l){
struct ListNode *pNode = l;
int count = 0;

while(pNode){
count++;
pNode = pNode->next;
}

return count;
}

int addTwoNumbers_1(struct ListNode *l1,int len1,struct ListNode *l2,int len2){
int carry = 0;
int sum = 0;

``````if(len1 == 0 || len2 == 0||
l1 == NULL || l2 == NULL){
return 0;
}

if(len1>len2){
sum = carry + l1->val;
l1->val = sum%10;
}

if(len1 == len2){
sum = carry + l1->val + l2->val;
l1->val = sum%10;
}

if(len1<len2){
sum = carry + l2->val;
l2->val = sum%10;
}

carry = sum/10;

return carry;
``````

}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int len1 = 0;
int len2 = 0;
int carry = 0;
struct ListNode *pNode = NULL;

``````len1 = getListLength(l1);
len2 = getListLength(l2);

if(len1>len2){
pNode = l1;
}

if(len1<=len2){
pNode = l2;
}

if(carry>0){
head = (struct ListNode *)malloc(sizeof(struct ListNode));