LeetCode445. 两数相加 II

☆☆思路：栈 + 头插法。本题要求不能对节点进行翻转，那么对于逆序处理，首先应该想到数据结构【栈】。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 不能对节点进行翻转，故用到数据结构【栈】
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        // 【头插法】 得到 翻转后的结果链表
        ListNode head = null;
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int x = stack1.size() == 0 ? 0 : stack1.pop();
            int y = stack2.size() == 0 ? 0 : stack2.pop();
            int temp = x + y + carry;
            carry = temp / 10;
            ListNode node = new ListNode(temp % 10);
            node.next = head;
            head = node;
        }
        if (carry == 1) {
            ListNode node = new ListNode(carry);
            node.next = head;
            head = node;
        }
        return head;
    }
}