有人帮我找出这段代码哪里错了吗？

Question

我正在尝试解决这个问题 leetcode 问题 C 语言，这是我想出的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

#include <math.h>

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *temp;
    struct ListNode *sum = NULL;  
    int num1 = 0;
    int num2 = 0;
    temp = l1;
    int n = 0;
    int i = 0;
    while (temp != NULL) {
        num1 = num1 + (temp->val * pow(10, i));
        i++;
        temp = temp->next;
    }
    temp = l2;
    i = 0;
    while (temp != NULL) {
        num2 = num2 + (temp->val * pow(10, i));
        i++;
        temp = temp->next;
    }
    int add = num1 + num2;
    int tem = add;
    i = 0;
    for (i = 0; tem > 0; i++) {
        tem = tem / 10;
    }
    if (add == 0) {
       struct ListNode *new = malloc(sizeof(struct ListNode));  
       new->val = 0;
       new->next = sum;
       sum = new;
    }
    while (add > 0 && i > 0) {
       struct ListNode *new = malloc(sizeof(struct ListNode));  
       new->val = add / pow(10, (i - 1));
       new->next = sum;
       i--;
       add = add % (int)(pow(10, i));
       sum = new;
    }
    return sum;
} 

我不明白为什么测试用例 l1 = [9]; 的输出为空 l2 = [1,9,9,9,9,9,9,9,9,9]。它在许多测试用例中都是正确的，但问题似乎出在 add 是 10 的倍数（可能）的测试用例中。请帮忙。

Answer 1

使用

ListNode

的要点是支持任意大的值。当您将值存储在

int num1

和

int num2

中时，整个目的就失败了，因为它仅限于

INT_MAX

，在我的系统上是

2147483647

（10 位数字）并且大于

num2

。有符号溢出是未定义的行为。

由于每个数字包含的信息少于 4 位，因此我为每个

unsigned char

使用了

int

（1 字节）而不是

ListNode::val

（在我的系统上为 4 字节）。

（未修复）

createDigit()

可以依赖调用者来初始化

next

。在这种情况下，

createNumber()

和

addTwoNumbers()

会在返回之前执行

tail->next = NULL

。这会更快但不太安全。

（不固定）

free()

两个参数以及

addTwoNumbers()

中

main()

的返回值。

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

// head of list is the least significant digit
struct ListNode {
    unsigned char val;
    struct ListNode *next;
};

struct ListNode *createDigit(struct ListNode *next, unsigned char val) {
    struct ListNode *newNode = malloc(sizeof *newNode);
    if(!newNode) {
        fprintf(stderr, "malloc failed\n");
        return NULL;
    }
    newNode->val = val;
    newNode->next = NULL;
    if(next) next->next = newNode;
    return newNode;
}

struct ListNode *createNumber(size_t n, const unsigned char vals[n]) {
    if(!n) return NULL;
    struct ListNode *head = NULL;
    for(struct ListNode *tail = NULL; size_t i = 0; i < n; i++) {
        tail = createDigit(tail, vals[i]);
        if(!head) head = tail;
    }
    return head;
}

void printNumber(const struct ListNode *n) {
    for(; n; n = n->next)
        printf("%d", n->val);
    printf("\n");
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL;
    unsigned char carry = 0;
    for(struct ListNode *tail = NULL; l1 || l2 || carry; l1 = l1 ? l1->next : NULL, l2 = l2 ? l2->next : NULL) {
        unsigned char sum = (l1 ? l1->val : 0) +
            (l2 ? l2->val : 0) +
            carry;
        tail = createDigit(tail, sum % 10);
        if(!head) head = tail;
        carry = sum / 10;
    }
    return head;
}

int main(void) {
    printNumber(
        addTwoNumbers(
            createNumber(1, (unsigned char []) {9}),
            createNumber(10, (unsigned char []) {1,9,9,9,9,9,9,9,9,9})
        )
    );
}

和示例输出：

00000000001

Answer 2

您的方法是不够的：列表可能表示超出类型

int

或所有可用整数类型范围的数字，因为列表被指定为最多具有 100 个节点。对于长度超过 9 或 10 个节点的列表，将列表转换为其表示的数字将产生未定义的行为。使用

pow

等浮点函数来执行整数计算通常是不合适的并且容易出错。

您应该为每个数字分配一个节点的新列表，其中包含参数列表的相应数字的总和，减少模 10 并将进位传播到下一个节点。

当到达其中一个列表的末尾时，继续传播另一个列表的进位，并在到达该列表的末尾时停止，分配一个额外的进位节点仍然不为零。

请注意，问题陈述并未指定您应该分配一个新列表，并且由于参数未指定为

const struct ListNode *

，因此您可以决定修改其中一个列表并返回指向其头节点的指针。通过将其中一个参数指定为

const

而不是另一个参数，可以使这一点更加明确。

这是一个简单的解决方案：

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *head = NULL;  
    struct ListNode *tail = NULL;  
    int carry = 0;
    while (l1 || l2 || carry) {
        struct ListNode *node = malloc(sizeof(*node));
        if (node == NULL) {
            /* allocation error: free partially allocated number and
             *  return NULL.
             */
            while (head) {
                node = head;
                head = head->next;
                free(node);
            }
            break;
        }
        node->next = NULL;
        /* compute the value of the sum digit and update the carry */
        int digit = carry;
        if (l1) {
            digit += l1->val;
            l1 = l1->next;
        }
        if (l2) {
            digit += l2->val;
            l2 = l2->next;
        }
        node->val = digit % 10;
        carry = digit / 10;
        /* append the node */
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return head;
}