题目：给你两个 非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

关键词

• 进位
• 数字溢出

用数组存放，高位补零：

import java.util.ArrayList;

//溢出问题
public class Blank {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        while (l1 != null) {
            arr1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            arr2.add(l2.val);
            l2 = l2.next;
        }
        int len1 = arr1.size();
        int len2 = arr2.size();
        int len = Math.max(len1, len2) + 1;
        int[] num1 = new int[len];
        int[] num2 = new int[len];
        for (int i = 0; i < len; i++) {
            if (i + len1 < len)
                num1[i] = 0;
            else
                num1[i] = arr1.get(i + len1 - len);
            if (i + len2 < len)
                num2[i] = 0;
            else
                num2[i] = arr2.get(i + len2 - len);
        }
        int[] res = new int[len];
        int flag = 0;
        for (int index = len - 1; index >= 0; index--) {
            int sum = num1[index] + num2[index] + flag;
            res[index] = sum % 10;
            flag = sum / 10;

        }
        ListNode sumlist = new ListNode(res[0]);
        ListNode ans = sumlist;
        for (int i = 1; i < len; i++) {
            sumlist.next = new ListNode(res[i]);
            sumlist = sumlist.next;
        }
        return res[0] == 0 ? ans.next : ans;
    }
}

用栈

注意stack用.isEmpty（）方法判断。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> sum = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int flag = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || flag == 1) {
            int temp = 0;
            if(!stack1.isEmpty() && !stack2.isEmpty())
                temp = stack1.pop() + stack2.pop() + flag;
            else if(!stack1.isEmpty())
                temp = stack1.pop() + flag;
            else if(!stack2.isEmpty())
                temp = stack2.pop() + flag;
            else
                temp = flag;
            sum.push(temp % 10);
            flag = temp / 10;
        }
        ListNode sumlist = new ListNode(sum.pop());
        ListNode ans = sumlist;
        while (!sum.isEmpty()) {
            sumlist.next = new ListNode(sum.pop());
            sumlist = sumlist.next;
        }
        return ans;
    }
}