【每日一题】445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

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

提示：

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        int flag = 0;
        ListNode tmp = l1;
        ListNode pre = l1;
        while(l1!=null || l2!=null) {
            int add1 = l1 == null ? 0 : l1.val;
            int add2 = l2 == null ? 0 : l2.val;
            int sum = flag+add1+add2;
            flag = sum/10;
            sum = sum%10;
            if(l1 != null) {
                if(l1 != tmp) pre = pre.next;
                l1.val = sum;
                l1 = l1.next;
            } else {
                ListNode x = new ListNode(sum);
                pre.next = x;
                pre = x;
            }
            if(l2 != null) l2 = l2.next;
        }
        if(flag != 0) {
            ListNode x = new ListNode(flag);
            pre.next = x;
            pre = x;
        }
        l1 = reverse(tmp);
        return l1;
    }
    public ListNode reverse(ListNode l1) {
        ListNode pre = l1;
        ListNode now = l1.next;
        ListNode tmp;
        while(now != null) {
            tmp = now.next;
            now.next = pre;
            pre = now;
            now = tmp;
            if(tmp == null) break;
        }
        l1.next = null;
        l1 = pre;
        return l1;
    }
}

        今天是一道中等题。还是链表相关的。实际上和昨天的题目差不多。

        今天这道题仍然是链表相关的加法题。但今天这道题就没昨天那么顺了。最快想到的思路应该就是反转链表了。反转链表，之后再使用昨天的方法进行相加。博主这里直接使用l1链表来存储结果。由于是链表，要注意null的情况。所以需要一个pre的指针来指向l1的前一个，这里是由于用l1来存储结果，如果l1是位数较小的数，那么就需要新建链表结点。所以需要一个pre来存住链表的最后一个位置，而l1则可以继续作为判断的标准。这样全加完之后，有可能有进位，就需要再对flag最后处理一次。处理完反转链表即可。

        这是通过的情况：

 

        那么，问题来了？不能反转链表的话，应该怎么做？首先，我们注意到这里是从头部开始。加法运算是从尾部加上来。那反转顺序会想到什么？栈！，先进后出的数据结构。我们可以创建两个栈，把所有数字都放入这两个栈， 再逐个取出，相加，计算进位。并使用头插的方法创建链表（不要思维定式了，觉得链表next就只能往后加。）这样就可以实现不反转的解题啦。

        其他的解法，大家可以去力扣看看原题的题解。有更多解法也可以发在评论区，大家一起讨论。