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
题目数据保证列表表示的数字不含前导零

思路

可以使用“逐位相加”的方法来解决这个问题，逐个节点处理两个链表中的每一位数字，并考虑进位问题。

1. 初始化一个伪头节点 (result) 用于存储结果链表的起点，并设置一个指针 (current) 指向这个伪头节点。
2. 使用一个变量 carry 来跟踪每次相加后的进位。
3. 遍历两个链表的同时，对应位置的数字相加，并加上上次相加的 carry。
4. 将相加的结果对 10 取余得到当前节点的值，并将 carry 更新为相加结果除以 10 的值（即进位）。
5. 将结果添加到结果链表中，并移动指针。
6. 当两个链表都遍历完后，如果 carry 仍然不为 0，则将 carry 添加到结果链表的最后。
7. 最后返回伪头节点 (result) 的下一个节点，即结果链表的头节点。

• 时间复杂度:O(max(m,n))
• 空间复杂度:O(max(m,n))

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 创建一个伪头节点
    ListNode result = new ListNode(0);
    // 指针指向结果链表的当前位置
    ListNode current = result;
    // 进位
    int carray = 0;
    int sum;
    while (l1 != null || l2 != null) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        // 当前节点的总和加上进位
        sum = x + y + carray;
        carray = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
        // 移动到下一个节点
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }
    // 如果最后还有进位，添加一个新节点
    if (carray > 0) {
        current.next = new ListNode(carray);
    }
    return result.next;
}