使用链表添加 2 个数字 - 大数字失败 - C

Question

我在leetcode上发现了使用单链表将两个数字相加的问题。我还是个初学者。我写了一个代码，它适用于前几个测试用例，但它对更大的测试用例失败，例如

[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]

我的输出：

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

预计：

[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]

我的代码：

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

您的函数最初是错误的，至少因为列表可能包含太大的数字，无法以任何基本整数类型存储。所以例如在这个声明中

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

可能会溢出。

或者这个声明中的内存分配

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

产生内存泄漏。

还有这个代码片段

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

导致未定义的行为。

函数可以如下所示

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;
}

使用链表添加 2 个数字 - 大数字失败 - C

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

c

linked-list

sum

singly-linked-list

function-definition