Leetcode 中等问题（单链表）

Question

1561/1563 个测试用例通过

问题描述：

给您两个表示两个非负整数的非空链表。最高有效数字在前，每个节点都包含一个数字。将两个数字相加并以链表形式返回总和。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。问题链接： https: //leetcode.com/problems/add-two-numbers-ii/

您不需要向我提供代码（会有帮助），只需提供为什么我在接下来的问题中得到错误答案的答案。

void insert_begging(struct ListNode **root,unsigned __int128 val){
    struct ListNode *new_node = malloc(sizeof(struct ListNode));
    new_node->val = val;
    if(*root == NULL){
        new_node->next = NULL;
        *root = new_node;
        return;
    }
    new_node->next = *root;
    *root = new_node;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* result = NULL;
    struct ListNode* curr = l1;
    unsigned __int128  sum = 0;
    unsigned __int128 sum2 = 0;
    while(curr!=NULL){
        sum=sum*10+curr->val;
        curr=curr->next;
    }
    struct ListNode* curr2 = l2;
    while(curr2!= NULL){
        sum2=sum2*10+curr2->val;
        curr2=curr2->next;
    }
    unsigned __int128 rsum = sum+sum2;
    unsigned __int128  digit = 0;
    if(rsum == 0){
        struct ListNode* result = malloc(sizeof(struct ListNode));
        result->val = rsum;
        result->next = NULL;
        return result;
    }
    while (rsum > 0) {
        int digit = rsum % 10;
        insert_begging(&result, digit);
        rsum /= 10;
    }
    return result;
}

所以我花了1个小时试图解决这个问题，但没有成功

这是我失败的测试：

l1 = [2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
l2 = [5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]

结果应该是：

[8,0,7,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,7,2,4,3,8]

首先，即使使用 unsigned long long 类型，我也会遇到 int 溢出，所以我将其更改为 unsigned __int128 但我得到了这个：

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

Answer 1

如果我们初学者不互相帮助，没有人会帮助我们。:)

显然，基本整数类型的对象都无法容纳如此大的数字。

因此，在基本整数类型的对象中构建数字的方法不起作用。

一种简单的方法可以如下所示，如下面的演示程序所示。

另一种更有效的方法是首先使用传递的列表之一以相反的顺序构建结果列表，然后添加第二个列表，然后再次反转结果列表。

这是使用简单方法的演示程序。

#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    unsigned int digit;
    struct ListNode *next;
};

void clear( struct ListNode **head )
{
    while (*head)
    {
        struct ListNode *current = *head;
        *head = ( *head )->next;
        free( current );
    }
}

void assign( struct ListNode **head, const unsigned int a[], size_t n )
{
    clear( head );

    while (n--)
    {
        *head = malloc( sizeof( struct ListNode ) );
        ( *head )->digit = *a++;
        ( *head )->next = NULL;
        head = &( *head )->next;
    }
}

FILE * display( const struct ListNode *head, FILE *fp )
{
    if (head == NULL)
    {
        fputc( '0', fp );
    }
    else
    {
        for (; head != NULL; head = head->next)
        {
            fputc( head->digit + '0', fp );
        }
    }

    return fp;
}

struct ListNode * addTwoNumbers( const struct ListNode *head1, const struct ListNode *head2 )
{
    const unsigned int Base = 10;

    struct ListNode *result = NULL;

    unsigned int carry = 0;

    const struct ListNode *last1 = NULL, *last2 = NULL;

    while (  last1 != head1 && last2 != head2 )
    {
        const struct ListNode *current1 = head1;

        while (current1->next != last1)
        {
            current1 = current1->next;
        }

        const struct ListNode *current2 = head2;

        while (current2->next != last2)
        {
            current2 = current2->next;
        }

        struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
        tmp->digit = ( current1->digit + current2->digit + carry ) % Base;
        tmp->next = result;
        result = tmp;

        carry = ( current1->digit + current2->digit + carry ) / Base;

        last1 = current1;
        last2 = current2;
    }

    while (last1 != head1)
    {
        const struct ListNode *current1 = head1;

        while (current1->next != last1)
        {
            current1 = current1->next;
        }

        struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
        tmp->digit = ( current1->digit + carry ) % Base;
        tmp->next = result;
        result = tmp;

        carry = ( current1->digit + carry ) / Base;

        last1 = current1;
    }

    while (last2 != head2)
    {
        const struct ListNode *current2 = head2;

        while (current2->next != last2)
        {
            current2 = current2->next;
        }

        struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
        tmp->digit = ( current2->digit + carry ) % Base;
        tmp->next = result;
        result = tmp;

        carry = ( current2->digit + carry ) / Base;

        last2 = current2;
    }

    if (carry)
    {
        struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
        tmp->digit = carry;
        tmp->next = result;
        result = tmp;
    }

    return result;
}

int main( void )
{
    unsigned int a1[] =
    {
        2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 9
    };
    const size_t N1 = sizeof( a1 ) / sizeof( *a1 );

    unsigned int a2[] =
    {
        5, 6, 4, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 9, 9, 9, 9
    };
    const size_t N2 = sizeof( a2 ) / sizeof( *a2 );

    struct ListNode *head1 = NULL;
    struct ListNode *head2 = NULL;

    assign( &head1, a1, N1 );
    assign( &head2, a2, N2 );

    fputc( '\n', display( head1, stdout ) );
    fputc( '\n', display( head2, stdout ) );

    struct ListNode *result = addTwoNumbers( head1, head2 );

    fputc( '\n', display( result, stdout ) );

    clear( &result );
    clear( &head2 );
    clear( &head1 );
}

程序输出是

2432432432432432432432432432432432432432432432432432432432439
5642432432432432432432432432432432432432432432432432432439999
8074864864864864864864864864864864864864864864864864864872438

例如，如果第一个列表包含数字

99999999999999999999

第二个列表包含数字

1

那么结果将是

100000000000000000000

addTwoNumbers如果引入一个将新节点推送到列表开头的附加函数，则可以使该函数更具可读性。

例如

struct ListNode * push_front( struct ListNode *head, unsigned int digit )
{
    struct ListNode *tmp = malloc( sizeof( struct ListNode ) );

    tmp->digit = digit;
    tmp->next  = head;

    return tmp;
}

struct ListNode * addTwoNumbers( const struct ListNode *head1, const struct ListNode *head2 )
{
    const unsigned int Base = 10;

    struct ListNode *result = NULL;

    unsigned int carry = 0;

    const struct ListNode *last1 = NULL, *last2 = NULL;

    while (  last1 != head1 && last2 != head2 )
    {
        const struct ListNode *current1 = head1;

        while (current1->next != last1)
        {
            current1 = current1->next;
        }

        const struct ListNode *current2 = head2;

        while (current2->next != last2)
        {
            current2 = current2->next;
        }

        result = push_front( result, ( current1->digit + current2->digit + carry ) % Base );

        carry = ( current1->digit + current2->digit + carry ) / Base;

        last1 = current1;
        last2 = current2;
    }

    while (last1 != head1)
    {
        const struct ListNode *current1 = head1;

        while (current1->next != last1)
        {
            current1 = current1->next;
        }

        result = push_front( result, ( current1->digit + carry ) % Base );

        carry = ( current1->digit + carry ) / Base;

        last1 = current1;
    }

    while (last2 != head2)
    {
        const struct ListNode *current2 = head2;

        while (current2->next != last2)
        {
            current2 = current2->next;
        }

        result = push_front( result, ( current2->digit + carry ) % Base );

        carry = ( current2->digit + carry ) / Base;

        last2 = current2;
    }

    if (carry)
    {
        result = push_front( result, carry );
    }

    return result;
}