023-两数相加（虚拟头节点）

问题重述

给定两个非空的链表，表示两个非负整数。链表中每个节点存储一个数字，且数字是逆序存储的（即链表的第一个节点是个位数，第二个节点是十位数，依此类推）。要求将这两个数相加，并返回一个同样以逆序方式存储的和的链表。

示例

输入：

• l1 = [2, 4, 3] （表示 342）
• l2 = [5, 6, 4] （表示 465）

输出：

• [7, 0, 8] （因为 342 + 465 = 807，逆序存储为 7 -> 0 -> 8）

解决思路

1. 初始化：

   • 创建一个虚拟头节点（dummy），简化链表操作。
   • 初始化 current 指针指向 dummy。
   • 初始化进位 carry 为 0。

2. 遍历链表：

   • 同时遍历 l1 和 l2，直到两个链表都遍历完且进位 carry 为 0。
   • 每次取出当前节点的值（如果链表已遍历完，则取 0）。
   • 计算 sum = val1 + val2 + carry。
   • 更新 carry = Math.floor(sum / 10)。
   • 创建新节点，值为 sum % 10，并链接到 current.next。
   • 移动 current 到新节点。
   • 移动 l1 和 l2（如果存在）。

3. 处理剩余的进位：

   • 如果遍历完链表后 carry > 0，则额外添加一个节点。

4. 返回结果：

   • dummy.next 就是新链表的头节点。

JavaScript 实现

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

function addTwoNumbers(l1, l2) {
    let dummy = new ListNode(0); // 虚拟头节点
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;

        const sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10); // 计算进位
        current.next = new ListNode(sum % 10); // 新节点
        current = current.next; // 移动指针

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next; // 返回真正的头节点
}

测试示例

// 示例测试
const l1 = new ListNode(2, new ListNode(4, new ListNode(3))); // 2 -> 4 -> 3 (342)
const l2 = new ListNode(5, new ListNode(6, new ListNode(4))); // 5 -> 6 -> 4 (465)

const result = addTwoNumbers(l1, l2); // 7 -> 0 -> 8 (807)

// 打印结果
let output = [];
let node = result;
while (node) {
    output.push(node.val);
    node = node.next;
}
console.log(output); // [7, 0, 8]

复杂度分析

• 时间复杂度：O(max(n, m))，其中 n 和 m 分别是 l1 和 l2 的长度。
• 空间复杂度：O(max(n, m))，新链表的长度最多为 max(n, m) + 1（如果最后有进位）。

总结

• 使用虚拟头节点简化链表操作。
• 逐位相加，并处理进位。
• **遍历直到两个链表都结束且进位为 0**。
• 返回 dummy.next 作为结果链表的头节点。