#2. 两数相加

2. 两数相加给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

**输入：**l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] **解释：**342 + 465 = 807.

示例 2：

**输入：**l1 = [0], l2 = [0] 输出：[0]

示例 3：

**输入：**l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

解答

python 版本

solution.py

java 版本

Solution.java

注释

当需要对两个逆序存储的链表进行相加时，可以使用以下 Java 代码来实现：

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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

这段代码中，我们使用了一个 dummyHead 来简化对结果链表的处理。然后我们使用 p 和 q 分别指向两个输入的链表 l1 和 l2，并使用 carry 变量来记录进位。我们遍历两个链表，将对应位置的数字相加，并将结果存储到新的链表中，同时更新进位。最后，如果最高位有进位，则需要在结果链表的最后添加一个节点来存储进位的值。

希望这段代码能够帮助到你。如果有任何疑问，欢迎随时向我提问。

当需要对两个逆序存储的链表进行相加时，我们可以使用一个类似于竖式加法的方法来实现。我们从两个链表的头部开始，逐个将对应位置的数字相加，并将结果存储到新的链表中。如果有进位，则需要将进位加到下一个位置的数字上。

以下是对上面代码的详细解释：

我们首先定义了一个 ListNode 类，用来表示链表的节点。每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。
然后我们定义了一个 addTwoNumbers 方法，该方法接受两个输入参数 l1 和 l2，分别表示需要相加的两个链表。
我们创建了一个名为 dummyHead 的虚拟头节点，并初始化 curr 指针指向它。这样做是为了简化对结果链表的处理。
我们使用两个指针 p 和 q 分别指向输入链表 l1 和 l2 的头部，并使用一个变量 carry 来记录进位的值，初始值为 0。
我们使用一个 while 循环来遍历两个链表，直到 p 和 q 都为 null。在循环中，我们首先分别获取 p 和 q 指向的节点的值（如果存在），如果节点不存在，则将其值设为 0。
然后我们将 p 和 q 指向的节点的值以及进位值相加，得到 sum。我们将 sum 对 10 取余数作为新节点的值，并将 sum 除以 10 得到的商作为新的进位值。
我们创建一个新的节点，将 sum 对 10 取余数作为节点的值，并将该节点链接到结果链表的末尾。然后将 curr 指针移动到新添加的节点上。
如果 p 和 q 指向的节点存在，则将 p 和 q 指针分别移动到下一个节点；如果其中一个链表已经遍历完了，那么将其值设为 0，以便继续相加。
最后，我们检查进位值 carry 是否大于 0，如果是，则在结果链表的末尾再添加一个节点，节点的值为 carry。
最后，我们返回 dummyHead 的下一个节点，即为相加后的结果链表的头节点。

这样，我们就完成了对两个逆序存储的链表进行相加的操作。希望这样的详细解释能够帮助你理解这段代码的实现原理。如果你有任何疑问，欢迎随时向我提问。

当需要对两个逆序存储的链表进行相加时，我们可以使用以下 Python 代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummyHead = ListNode(0)
    p, q, curr = l1, l2, dummyHead
    carry = 0
    while p or q:
        x = p.val if p else 0
        y = q.val if q else 0
        sum = x + y + carry
        carry = sum // 10
        curr.next = ListNode(sum % 10)
        curr = curr.next
        if p: p = p.next
        if q: q = q.next
    if carry > 0:
        curr.next = ListNode(carry)
    return dummyHead.next

在这段代码中，我们首先定义了 ListNode 类，然后定义了 addTwoNumbers 方法来实现链表相加的功能。这段代码的逻辑与之前提到的解释是一致的，只是用 Python 语法重新实现了一遍。

希望这个 Python 版本的代码能够帮助你更好地理解这个算法的实现。如果你有任何疑问，欢迎随时向我提问。

解答

python 版本​

java 版本​

注释

python 版本

java 版本