两数相加 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

进阶：如果输入链表不能翻转该如何解决？

代码结果

运行时间: 72 ms, 内存: 14.9 MB

/*
 * 思路：
 * 1. 使用Java Stream将链表转换为栈
 * 2. 使用循环将栈元素出栈相加
 * 3. 将结果转换为链表
 */
 
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = Stream.iterate(l1, node -> node != null, node -> node.next)
                                       .map(node -> node.val)
                                       .collect(Collectors.toCollection(Stack::new));
        Stack<Integer> stack2 = Stream.iterate(l2, node -> node != null, node -> node.next)
                                       .map(node -> node.val)
                                       .collect(Collectors.toCollection(Stack::new));
        ListNode result = null;
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int sum = carry;
            if (!stack1.isEmpty()) sum += stack1.pop();
            if (!stack2.isEmpty()) sum += stack2.pop();
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = result;
            result = node;
        }
        return result;
    }
}

解释

方法:

这道题的思路是利用栈来模拟数字的加法过程。由于链表的最高位在链表的开始位置，我们可以使用栈将链表中的数字按顺序存储，这样栈顶的元素就是数字的最低位。接着我们可以像手动计算两个数字之和那样，从栈顶开始逐位相加，并处理进位。最后，我们将结果构造成一个新的链表并返回。

时间复杂度:

O(m+n)

空间复杂度:

O(m+n)

代码细节讲解

🦆

为什么在处理两个链表的数字时选择使用栈而不是其他数据结构？

▷

使用栈的主要原因是栈具有后进先出（LIFO）的特性，这使得可以从链表的末尾（即数字的最低位）开始进行加法运算。链表的头部代表数字的最高位，直接操作链表会更复杂，因为需要反复遍历找到链表的尾端。使用栈可以简化这一过程，先将所有数字压入栈中，然后再逐个弹出，这样可以轻松地从最低位向最高位进行计算，便于处理进位。

🦆

在`addTwoNumbers`函数中，当两个栈都为空但仍存在进位时，你是如何处理的？

▷

在`addTwoNumbers`函数中，即使两个数字对应的栈都已经为空，仍然可能存在未处理的进位。在循环的条件中，除了检查栈是否为空外，还包括`carry == 1`。这确保了即使栈为空，只要还有进位存在，就会继续执行循环。如果进位存在（`carry == 1`），则会创建一个新的节点，其值为1（即进位的值），然后将这个节点加到结果链表的最前端。

🦆

你是如何确保在从栈中弹出元素时不会出现尝试从空栈中弹出的错误？

▷

为了防止从空栈中弹出元素的错误，代码中使用了条件表达式来检查栈是否为空。在计算总和时，只有当栈非空（即`s1`或`s2`非空）时，才会尝试从栈中弹出元素。具体的表达式是`s1.pop() if s1 else 0`和`s2.pop() if s2 else 0`，这意味着如果栈为空，则代替的值为0。这样即使栈为空，也能保证代码的正常运行而不会引发错误。

🦆

如果两个输入链表长度不同，这种方法是否仍然有效？在实现中有什么特别处理吗？

▷

即使两个链表的长度不同，这种使用栈的方法仍然有效。在实现中没有特别处理这种长度不等的情况，因为栈自然地处理了这种情况。较短的链表对应的栈会更早变空。一旦某个栈为空，代码通过上述的条件表达式（`s1.pop() if s1 else 0`和`s2.pop() if s2 else 0`）自动将该栈的贡献视为0。这样可以继续加法运算直到两个栈都为空。因此，本方法自然地适应了不同长度的输入链表。

两数相加 II

题目描述

代码结果

解释

代码细节讲解

相关问题

两数相加