LeetCode.445.Add Two Numbers II 两数相加 II

题目描述

445 Add Two Numbers II
https://leetcode-cn.com/problems/add-two-numbers-ii/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

---

解题过程

相似题目
LeetCode.002.Add Two Numbers 两数相加
LeetCode.445.Add Two Numbers II 两数相加 II

题目要求不能修改原链表，否则的话可以先分别反转两个链表，然后双指针从前往后相加，结果链表再反转即可。

用两个栈，分别把两个链表 push 进去，然后两两 pop 出栈相加后插入到结果链表的头部。

需要注意的点：
1、用一个不存储数据的 dumpHead 头结点作为新链表的头结点，可以简化操作，避免第一个结点特例的判断，最后返回 dumpHead.next 即可。
2、只要l1非空、l2非空、进位不为0三个条件中任意一个满足，就继续循环，在循环内如果链表为空用0代替。这一条是当初我 002 题时从别人那学的一招，现在我也会了。

时间复杂度O(max(m,n))，空间复杂度 O(m+n)

private static class SolutionV2020 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode dumbHead = new ListNode(0);
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            carry += (!stack1.isEmpty() ? stack1.pop() : 0) + (!stack2.isEmpty() ? stack2.pop() : 0);
            ListNode listNode = new ListNode(carry % 10);
            // 头插法插入到 dumbHead 之后
            listNode.next = dumbHead.next;
            dumbHead.next = listNode;
            carry /= 10;
        }
        return dumbHead.next;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_445_AddTwoNumbers2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_445_AddTwoNumbers2.java

---