力扣Top100刷题系列之两数相加

老规矩，先来欣赏下评论区的奇人妙事~

评论一

评论二

2 . 两数相加

难度中等7126

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

img

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

++++

方法一：

思路分析：首先写起来最简单的方法就是先遍历两次链表，分别把它们实际表示的数计算出来然后直接相加，相加后再次把这个数以链表的形式再串起来。为了避免溢出我特意使用了unsigned long long 类型，但是可惜还是在最后的倒数第三个示例溢出了。（其实要是用Python这样写的话应该是没问题的，毕竟Python不存在这种溢出的问题）

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        unsigned long long result = 0;
        unsigned long long mul = 1;
        while(l1){  //先把第一个链表表示的数相加
            result += mul* l1->val;
            mul*=10;
            l1 = l1->next;
        }
        mul=1;
        while(l2){  //第二个链表表示的数也加到结果上
            result += mul* l2->val;
            mul*=10;
            l2 = l2->next;
        }      
        ListNode* resultptr = new ListNode();
        ListNode* res = resultptr;
        if(result==0)
            return resultptr;
        while(result){   //生成一个新的链表
            res->next = new ListNode(result%10);
            res = res->next;
            result = result/10;   
        }
        return resultptr->next;
    }

转换成整数_出现溢出

方法二：

思路分析：第二种的思路效果还不错，这个题已经将题目简化了，虽然写着是一道中等难度的题。它的链表采用的是整数的逆序，它的原型是大数加法，用的思路也是模拟法，就是模拟各个位数相加，自己把每次需要进一的存起来加到下一位，不过需要自己把两个大数拆开然后再逆着保存，有兴趣的读者可以在做完这个题之后去那道题练习一下。

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = new ListNode();
        if(l1 == nullptr || l2 == nullptr){ //判空，防止出现坑
            return l1==nullptr?l2:l1;
        }
        int tmp = 0;
        ListNode* r = res;

        while(l1 || l2){  //直到两个链表都指向NULL为止
            if(l1)
               tmp += l1->val;


            if(l2)
                tmp += l2->val;


                if(l1==nullptr && l2 == nullptr){
                    r = nullptr;
                    break;
                }                

                r->next = new ListNode(tmp%10);  //模拟各个为相加，然后把减10以后的数放到新链表中
                tmp = tmp/10;
                r = r->next;
                if(l1)    //千万要记得移到下个链表，否则将是死循环
                    l1 = l1->next;
                if(l2)
                    l2 = l2->next;              
        }
        if(tmp > 0)  //防止加到最高位仍然还有进1的没有考虑
        {
            r->next = new ListNode(tmp%10);            
        }

        return res->next;
    }    

大数加法模拟

总结

这个题最重要思想就是模拟大数加法，因为在重型语言例如C,C++和Java等这种有着明确的数据类型的语言，在编译的时候就明确了分配内存的大小，即在编译时期确定的，但是在运行期间需要放入的东西是不确定的，因此会出现溢出的情况，所以有时候回归原始也不失为一个好的思路，用模拟的方法来解决直接相加的问题，在以后的工作中很可能也会遇到。