欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-24 12:45:12
...


Leetcode 2 medium\color{#FF7D00}{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;

【小白爬Leetcode2】1.10 两数相加Add Two Numbers
\color{#FF0000}{其实我这里还有个问题,不知道是不是错误:}
题目要求返回全新的链表,而我遇到了l1或者l2遍历到底的情况,就直接返回另一个没到底的了。比如说1+284,那么返回的新链表的个位数之后的十位数和百位数都是原链表284的节点

思路二 一次循环搞定

t\color{#FF0000}{做完之后去评论区瞅了一眼,的确不需要两次循环,只需要维护一个进位变量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不了的例子:
【小白爬Leetcode2】1.10 两数相加Add Two Numbers
为什么呢?因为这个例子需要连续进位!十位进位完之后,还要向百位进位,而我对于进位的处理是在下层递归结束之后进行的,且只考虑了进一位,自然无法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;
    }
};

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