添加两个数字：LeetCode

Question

给你两个非空链表，代表两个非负整数。这些数字以相反的顺序存储，并且每个节点都包含一个数字。将两个数字相加并以链表形式返回总和。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。

我确实在网上找到了这个问题的答案，但我需要帮助找出我的代码出了什么问题。我也知道我的代码在优化方面不是最好的，但接受任何帮助。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
                ListNode *p=l1, *q=l2;
        ListNode *sum= nullptr, *lastdigit= nullptr;
        int num1=0,num2=0;
        while(p!= nullptr)
        {
            int val1= p->val;
            num1=(10*num1)+val1;
            p=p->next;
        }
        cout<<num1<<endl;
        while(q!=nullptr)
        {
            int val2 = q->val;
            num2 =(10*num2)+val2;
            q=q->next;
        }
        cout<<num2<<endl;
        int sum_=num1+num2;
        int r= sum_%10;
            sum= new ListNode(r);
            sum_/=10;
        lastdigit = sum;
        while(sum_!=0)
        {
            int r= sum_%10;
            lastdigit->next= new ListNode(r);
            lastdigit=lastdigit->next;
            sum_/=10;
        }
        return sum;
    }
};

https://leetcode.com/problems/add-two-numbers/

Answer 1

您的代码将输入链表转换为整数，但这会带来两个问题：

1. 输入可能包含最多 100 个节点（数字）的链表，这超出了整数数据类型的范围。
2. 您的代码将第一个节点视为最高有效数字，而应将其视为最低有效数字。

要解决第二个问题，请按如下方式更改代码的第一个循环：

int pow10 = 1;
while (p!= nullptr) {
    int val1 = p->val;
    num1 += val1 * pow10;
    pow10 *= 10;
    p = p->next;
}

...对第二个循环执行相同的操作。

您从整数和构建结果列表的最后一个循环是正确的：您did将最低有效数字放入结果的头节点中。

当输入由小型链表（最多 9 个节点）组成时，上述更正将使您的代码正确运行。

为了真正解决这个挑战，你不能使用这个算法，因为第一个问题（

int

不能代表100位数字）。您确实应该将添加分解为一次添加列表中较小的块（大多数会使用one节点作为“块”），并跟踪从一个块到下一个块的结转，同时分块构建结果列表。

正如您所写的，您已经可以访问该解决方案，我不会在这里提供它。您也可以从同一挑战中的这个问题中获得灵感，但是 C#。