Add 2 Numbers using linked lists - fail with large numbers - C

Question

On leetcode I have found the problem of adding two numbers using singly linked lists. I'm still a beginner. I have written a code, which works for the first few testcases, but it fails with larger ones e.g.

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]

my output:

[-3,-4,-3,-5,-7,-7,-4,-5,-8,-6,-3,0,-2,-7,-3,-3,-2,-2,-9]

expected:

[6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]

my code:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    //extracting value of first list
    int cnt1 = -1;
    long long int sum1 = 0;
    struct ListNode *q = l1;
    while (q != NULL) {
        cnt1++;
        sum1 = sum1 + q->val * pow(10, cnt1);
        q = q->next;
    }
    printf("%d, %d\n", cnt1, sum1);

    //extracting value of second list
    int cnt2 = -1;
    long long int sum2 = 0;
    struct ListNode *p = l2;
    while (p != NULL) {
        cnt2++;
        sum2 = sum2 + p->val * pow(10, cnt2);
        p = p->next;
    }
    printf("%d, %d\n", cnt2, sum2);
    
    long long int finalSum = sum1 + sum2;
    printf("%d\n", finalSum);

    struct ListNode *retRoot = malloc(sizeof(struct ListNode));
    struct ListNode *t = malloc(sizeof(struct ListNode));
    
    //putting the final sum into the list

    long long int newSum;

    retRoot->val = finalSum % 10;
    retRoot->next = malloc(sizeof(struct ListNode));
    newSum = finalSum / 10;
    if (newSum == 0) {
        retRoot->next = NULL;
        return retRoot;
    }
    t = retRoot->next;
    while (newSum != 0) {
        //printf("newSum: %d\n", newSum);
        t->val = newSum % 10;
        newSum = newSum / 10;
        if (newSum == 0) break;
        t->next = malloc(sizeof(struct ListNode));
        t = t->next;
    }
    t->next = NULL;

    return retRoot;
}

Answer 1

Your function initially is wrong at least because a list can contain a too big number that can not be stored in any fundamental integer type. So for example in this statement

 sum1 = sum1 + q->val * pow(10, cnt1);

there can be an overflow.

Or the memory allocation in this declaration

struct ListNode *t = malloc(sizeof(struct ListNode));

produces a memory leak.

And moreover this code snippet

t = retRoot->next;
while (newSum != 0) {
    //printf("newSum: %d\n", newSum);
    t->val = newSum % 10;
    //...

results in undefined behavior.

The function can look the following way

struct ListNode * addTwoNumbers( const struct ListNode *l1, const struct ListNode *l2 )
{
    const int Base = 10;
    
    struct ListNode *head = NULL;
    struct ListNode **current = &head;
    
    int overflow = 0;
    
    for ( ; l1 != NULL || l2 != NULL; current = &( *current )->next )
    {
        *current = malloc( sizeof( struct ListNode ) );
        int sum = overflow;
        
        if ( l1 != NULL )
        {
            sum += l1->val;
            l1 = l1->next;
        }

        if ( l2 != NULL )
        {
            sum += l2->val;
            l2 = l2->next;
        }
        
        ( *current )->val = sum % Base;
        overflow = sum / Base;
        
        ( *current )->next = NULL;
    }

    if ( overflow )
    {
        *current = malloc( sizeof( struct ListNode ) );
        ( *current )->val = overflow;
        ( *current )->next = NULL;
    }

    return head;
}