每天一道算法题-两数相加

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

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

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

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

示例二：
输入：l1 = [0], l2 = [0]
输出：[0]

示例三：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

首先，题目说两个非空链表，每个节点存一位数字，而且是逆序存储的。比如，数字342会被存为2->4->3这样的链表。那我要把这样的两个链表相加，得到的结果同样用逆序的链表表示。并且，除了数字0之外，这两个数都不会以0开头。那输出的链表也应该符合这个条件，比如结果如果是0的话，就只能有一个节点。

那怎么做呢？我记得通常处理这种链表加法的时候，是模拟加法进位的过程。因为链表是逆序的，所以最低位在链表头，这样可以直接从头开始相加，处理进位。这应该比较直接。

那步骤大概是这样的：同时遍历两个链表，逐位相加，同时考虑进位。当其中一个链表遍历完时，继续处理剩下的节点，加上进位。最后如果还有进位，要新建一个节点。

比如例子中的情况：比如输入是2->4->3（342）和5->6->4（465），相加得到807，结果应该是7->0->8。那链表就是7->0->8。这个过程需要处理每一位相加，进位保存下来加到下一位。

那具体实现的话，我需要创建两个指针分别遍历两个链表，同时维护一个进位变量carry。每次取出两个节点的值相加，加上carry，然后计算当前位的值（sum%10）和新的进位（sum/10）。然后将当前位的值作为新节点添加到结果链表中。直到两个链表都遍历完，并且进位为0为止。

这里需要注意的情况是，当两个链表长度不一致的时候，较长的那个链表剩下的部分需要继续处理。比如一个链表已经遍历完，另一个还有节点，或者进位还存在的情况下要继续处理。

举个例子，比如链表1是9->9，链表2是9。那相加的话，结果应该是8->0->1。即99+9=108，逆序的话是8->0->1。这时候，当链表2遍历完后，链表1还有节点，这时候要继续处理剩下的节点，加上进位。

那如何实现呢？可以用循环，当链表1或链表2还有节点，或者进位不为零的时候继续循环。在循环中，每次取出当前节点的值，如果链表已经到头了，就取0。然后计算和，然后移动指针，如果链表还有下一个节点的话。

那现在考虑链表的遍历方式。比如，用while循环，条件是l1不为空或者l2不为空或者carry不为零。这样就能覆盖所有情况。

比如，初始化进位carry为0。然后，在每次循环中：

• 取l1的当前值，如果l1不为空，否则取0。
• 取l2的当前值，如果l2不为空，否则取0。
• 计算sum = val1 + val2 + carry。
• 计算新的carry = sum / 10。
• 创建新节点，值为sum %10。
• 将新节点连接到结果链表的末尾。
• 移动l1和l2的指针（如果存在的话）。

但是，这样处理的话，结果链表的构建需要维护一个当前指针，或者使用哑结点（dummy node）来简化操作。哑结点的下一个节点是真正的头节点，这样可以避免处理初始空链表的情况。

比如，初始化一个dummy节点，然后维护一个当前指针curr，初始指向dummy。每次生成新节点时，curr.next指向它，然后curr移动到下一个节点。这样最后返回dummy.next即可。

这样就能处理所有情况，包括最后的进位。例如，当所有节点都处理完了，但还有进位1，这时候需要新建一个节点。

那现在编写具体的代码步骤：

1. 创建一个哑结点dummy，curr指向dummy。
2. 初始化carry为0。
3. 当l1不为空，或l2不为空，或者carry不为0时循环：
   a. 获取l1的值，如果l1存在，否则为0。
   b. 获取l2的值，如果l2存在，否则为0。
   c. 计算sum = val1 + val2 + carry。
   d. 计算新的carry = sum /10。
   e. 创建新节点，值为sum %10。
   f. curr.next指向新节点，curr移动到next。
   g. 如果l1不为空，l1移动到l1.next。
   h. 如果l2不为空，l2移动到l2.next。
4. 返回dummy.next作为结果链表的头节点。

那这样的逻辑应该可以覆盖所有情况。

比如测试案例：

例子1：
输入：l1 = [2,4,3], l2 = [5,6,4]
相加结果：342 + 465 = 807 → 逆序是7->0->8。
按照步骤：
初始化carry为0。
第一次循环：
val1=2，val2=5，sum=7+0=7。carry=0，新节点7。curr指向它。l1和l2都移动到下一个。
第二次循环：
val1=4，val2=6，sum=10+0=10。sum%10=0，carry=1。新节点0。curr指向它。l1和l2移动到下一位。
第三次循环：
val1=3，val2=4，sum=3+4+1=8 → sum%10=8，carry=0。新节点8。此时l1和l2都到头了，但循环继续吗？因为此时carry为0，但是此时循环的条件是l1或l2不为空或carry不为零。此时l1和l2都是空，carry为0，所以退出循环。
结果链表是7->0->8。正确。

另一个例子，其中一个链表较长：
比如l1是9->9->9，l2是9->9。即数字是999和99，相加是1098。逆序存储的话，链表应该是8->9->0->1。
处理过程：
初始carry=0。
第一次循环：9+9=18+0=18 → sum%10=8，carry=1。新节点8。l1和l2都移动。
第二次循环：9+9+1=19 → sum%10=9，carry=1。l1移动，l2为空。
第三次循环：9+0+1=10 → sum%10=0，carry=1。此时l1还有吗？l1此时是第三个节点，处理完这次后，l1变为null。l2还是null，但carry是1。所以循环继续。
第四次循环：0+0+1=1 → sum%10=1，carry=0。创建节点1。此时所有条件都不满足，退出循环。结果链表是8->9->0->1。正确。

那这样处理是正确的。

那关于哑结点的使用，这样可以避免处理初始头节点为空的情况，简化代码。

现在考虑代码的实现，比如用Java的话：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}

这样应该可以正确处理所有情况。例如，当两个链表都处理完，但还有进位的情况，比如最后进位为1时，会生成一个新节点。

那这个解法的时间复杂度是O(max(m, n))，其中m和n是两个链表的长度，因为需要遍历两个链表的全部节点。空间复杂度是O(max(m, n))，因为需要创建结果链表，其长度最多为max(m,n)+1（比如最后进位的情况）。

那有没有特殊情况需要处理？比如两个链表都为空，但题目规定是非空的，所以不需要考虑。或者结果链表的前导零？题目说明除了数字0外，不会以0开头，所以比如结果为0的情况只能是0本身，也就是一个节点。这种情况会在循环中处理吗？

比如，输入是两个0的链表。则相加得到0，此时循环的条件是l1或l2不为空或carry不为零。初始时，l1和l2都是非空，所以进入循环：

val1=0，val2=0，sum=0+0+0=0，carry=0。创建节点0。然后l1和l2都移动到null。此时循环是否继续？此时，l1和l2都为空，carry为0，所以不进入循环。返回dummy.next是节点0。正确。

那没有问题。

另一个测试案例，比如l1是[9,9]，l2是[9]。相加得到18 + 9 = 99+9=108？或者原题中的例子是否应该更仔细？

比如，链表1是9->9，即99，逆序的话是99。链表2是9，即9。相加得到99+9=108。逆序存储的话应该是8->0->1。按照上述代码的处理：

第一次循环，sum是9+9+0=18 → sum%10=8，carry=1。节点8。l1移动，l2移动（到null）。
第二次循环，l1有节点9，val1=9，val2=0，sum=9+0+1=10 → sum%10=0，carry=1。节点0。l1移动（null）。
第三次循环，l1和l2都null，carry=1。sum=0+0+1=1 → sum%10=1，carry=0。节点1。此时循环结束。结果链表是8->0->1，正确。

综上，这个代码应该可以正确处理所有情况。

要将两个逆序链表表示的数字相加并返回同样格式的链表，可以按照以下步骤进行：

方法思路

1. 初始化：使用哑结点（dummy node）简化链表操作，并维护一个当前指针 curr 来构建结果链表。同时，用变量 carry 记录进位值。
2. 遍历链表：同时遍历两个链表，逐位相加：
   • 如果某个链表已遍历完，则其后续位的值视为0。
   • 计算当前位的和（包括进位），更新进位。
   • 将当前位的值作为新节点添加到结果链表中。
3. 处理剩余进位：若遍历结束后仍有进位，需添加新节点。

解决代码

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

代码解释

1. 哑结点初始化：dummy 节点简化链表头部的处理，curr 用于逐步构建结果链表。
2. 循环条件：l1 或 l2 未遍历完，或仍有进位时继续循环。
3. 计算当前位和进位：取两链表当前节点的值（若存在），加上进位计算总和，更新进位。
4. 添加新节点：将当前位的值（sum % 10）作为新节点，移动 curr。
5. 移动链表指针：若链表未遍历完，继续移动指针。
6. 返回结果：最终返回哑结点的下一个节点，即结果链表的头节点。

该方法时间复杂度为 O(max(m, n))，空间复杂度为 O(max(m, n))，能高效处理两数相加问题。