【小白爬Leetcode2】1.10 两数相加Add Two Numbers

Leetcode 2 $\color{#FF7D00}{medium}$medium

点击进入原题链接：LeetCode中国站

题目

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

中文描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路一 一次累加、一次进位(犯了一个错误)

思路很简单，第一遍while循环两个链表从个位开始一直往后加，第二遍while循环新的链表从个位开始进位，逢10进1 (我以前一直以为C++没有%真是愚蠢至极)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode res(0);
        ListNode* head = &res;
        
        while(l1&&l2)
        {
            head->next = new ListNode(l1->val+l2->val);
            head = head->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        if(l1){head->next=l1;}
        if(l2){head->next=l2;}
        
        head = &res;
        while(head)
        {
            if(head->val>=10){
                head->val %= 10;
                if(head->next){head->next->val+=1;}
                else{head->next = new ListNode(1);}
            }
            head = head->next;
        }
        return res.next;
    }
};

这里我还遇到过一个错误
stack-use-after-scope 就是栈区的数据都释放了还在用它。
遍历代码，发现是return写错了，因为ListNode res(0)只是个虚拟头节点，我最后是不用它的，所以我就没放在堆区，而我一开始的return写的是：

return &res;

这里res只是栈上的一个ListNode类，当这个addTwoNumbers函数的生命周期结束后它也就一起被编译器回收了，我还return &res就相当于return了一个野指针。实际上真正的答案是从res->next开始的，应该改为：

return res.next;

$\color{#FF0000}{其实我这里还有个问题，不知道是不是错误：}$其实我这里还有个问题，不知道是不是错误：
题目要求返回全新的链表，而我遇到了l1或者l2遍历到底的情况，就直接返回另一个没到底的了。比如说1+284，那么返回的新链表的个位数之后的十位数和百位数都是原链表284的节点

思路二 一次循环搞定

$\color{#FF0000}{做完之后去评论区瞅了一眼，的确不需要两次循环，只需要维护一个进位变量t}$做完之后去评论区瞅了一眼，的确不需要两次循环，只需要维护一个进位变量t

循环的条件无外乎两种：

1. l1或l2没有遍历完；
2. 还需要新增进位，比如1+99需要增加百位。

这对应了代码中的：

while (l1 != NULL || l2 != NULL || t != 0)

每轮循环都会new出下一个节点，当l1和l2都遍历完了之后，如果不需要进位，则在上一轮t/=10后，t应该为0，那么循环结束；否则如果需要进位，那么这一位是原来没有的，也需要new一个ListNode(t)，这个t由于跳过了l1和l2，恰恰就是上一轮的t/=10之后的t。

class Solution {
public: 
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(-1);
        ListNode* pre = dummyHead;
        int t = 0;
        while (l1 != NULL || l2 != NULL || t != 0) {
            if (l1 != NULL) {
                t += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                t += l2->val;
                l2 = l2->next;
            }
            pre->next = new ListNode(t % 10);
            pre = pre->next;
            t /= 10;
        }

        return dummyHead->next;
    }
};

思路三 递归实现

信心满满地写了一个递归如下，却在debug过程中发现之前写循环的时候有很多没有考虑到的东西：
先放出我写的这段递归代码：

1. 每一层递归，首先判断l1或者l2有没有遍历完，如果l1遍历完了直接返回l2;
2. 然后new一个当前节点，给当前节点赋上结果后余10的值；
3. 进行下一层递归；
4. 对下一层递归返回的结果进行进位操作：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1){return l2;}
        if(!l2){return l1;}
        ListNode* res = new ListNode(0);
        int sum = l1->val+l2->val;
        res->val = sum%10;
        res->next = addTwoNumbers(l1->next,l2->next);
        if(res->next){
        res->next->val += sum/10;
        }
        else{if(sum/10!=0){res->next = new ListNode(sum/10);}}
        return res;
    }
};

看起来天衣无缝，测试案例也莫得问题，但是…
OJ给我返回了一个handle不了的例子：

为什么呢？因为这个例子需要连续进位！十位进位完之后，还要向百位进位，而我对于进位的处理是在下层递归结束之后进行的，且只考虑了进一位，自然无法handle这个例子。

思考了一下对代码进行了一些补救：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1){return l2;}
        if(!l2){return l1;}
        ListNode* res = new ListNode(0);
        int sum = l1->val+l2->val;
        res->val = sum%10;
        res->next = addTwoNumbers(l1->next,l2->next);
        ListNode* cur = res;
        while(sum/10!=0)
        {
            if(cur->next){
                cur->next->val += sum/10;
                sum = cur->next->val;
                cur->next->val %= 10;
            }
            else{cur->next = new ListNode(sum/10);sum = cur->next->val;}
            cur = cur->next;
        }

        return res;
    }
};