【每日一题】Leetcode每日一题 - 两数相加

题目链接：https://leetcode.cn/problems/add-two-numbers/description

文章目录

• 错误做法
• 正确做法

错误做法

由于这题给到的链表顺序相对数字顺序来说是倒序的，我最初的想法是先把这个链表反转，然后遍历每一项的链表，使前面的计算结果 * 10 + 当前的值。

结果测试点里面有一个100000000000000000000000001这样的数据，所以就GG了，这是我原本的题解：

class Solution
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        // 首先实现反转列表
        ListNode *res1 = nullptr, *res2 = nullptr;
        ListNode *temp = l1, *temp2 = l2;
        // 如果temp不等于空
        while (temp != nullptr)
        {
            // 取出它的下一项，这么做的主要原因是取出下一项后最后一步temp需要重新指向下一项，temp的当前向的next会被我们指向res1
            ListNode* nextTemp = temp->next;
            // 将当前的下一项做为res1
            temp->next = res1;
            // 将temp整理好的顺序重新返还给res1
            res1 = temp;
            // 下次循环使用下一项进行循环
            temp = nextTemp;
        }

        while (temp2 != nullptr)
        {
            ListNode* nextTemp = temp2->next;
            temp2->next = res2;
            res2 = temp2;
            temp2 = nextTemp;
        }

        long long a = 0;
        long long b = 0;
        while (res1 != nullptr)
        {
            a = a * 10L + res1->val;
            res1 = res1->next;
        }

        while (res2 != nullptr)
        {
            b = b* 10L + res2->val ;
            res2 = res2->next;
        }
        long long c = a + b;

        if (c == 0)
        {
            return new ListNode(0);
        }

        ListNode* res = nullptr;
        ListNode* tail = nullptr;

        while (c != 0)
        {
            int m = c % 10;
            c = c / 10;
            // 创建一个新node
            ListNode* newNode = new ListNode(m);
            if (res == nullptr)
            {
                res = newNode;
                tail = res;
            }
            else
            {
                tail->next = newNode;
                tail = newNode;
            }
        }
        return res;
    }
};

正确做法

我的正确做法是参考了官方的题解了，因为我当时被这链表的顺序给折磨疯了就参考了一下题解才发现，给你倒序的原因就是你能够正好的计算每一位相加的结果，如果>=10了，再下一次计算加法的时候进位就好了。

但是我写完之后发现有一个9999999和9999的测试点又卡住了，经过梳理才发现原因是如果最后一位还有一个1没法再进位（就是加法算到头了）多余的一个进位肯定要写1，改了之后就过了

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = nullptr, *tail = nullptr;
        int carry = 0;
        while(l1 || l2) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            int c = a + b + carry;
            carry = c >= 10 ? 1 : 0;
            ListNode* t = new ListNode(c % 10);
            if(res == nullptr) tail = res = t;
            else tail = tail->next = t;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        if (carry == 1) tail = tail->next = new ListNode(1);
        return res;
    }
};