题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

1.题目关键字

• 两个非空链表
• 最高位在链表头
• 不会以0开头
• 不可以改变链表

2.解题思路

• 1.反转链表--->将题目转换成 以前做过的 两数相加问题
• 2.先进后出 想到的 首要数据结构 栈

代码实现 仅提供进阶版本 使用栈的方法

代码注意事项

• 1.两个栈分别存取不同链表数据
• 2.虚拟头结点会减少头插入的代码
• 3.最高位进位不要忘记判断

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                s1.push(l1.val);
                l1 = l1.next;
            }
            if (l2 != null) {
                s2.push(l2.val);
                l2 = l2.next;
            }
        }
        int mod = 0;
        //虚拟头结点
        ListNode res = new ListNode(-1);
        ListNode head = res;
        while (!s1.isEmpty() || !s2.empty()) {
            int num1 = s1.isEmpty() ? 0 : s1.pop();
            int num2 = s2.isEmpty() ? 0 : s2.pop();

            int temp = num1 + num2 + mod;
            mod = temp / 10;
            temp = temp % 10;
            head.next = new ListNode(temp, head.next);
        }
        //最高位进位问题
        if (mod != 0) {
            head.next = new ListNode(mod, head.next);
        }
        return res.next;
    }