这是 LeetCode 经典的“两数相加”问题。下面提供 JavaScript 的解题思路和代码。

解题思路

由于链表是逆序存储的（个位在头部），我们可以直接从头开始遍历两个链表，模拟竖式加法的过程：

1. 同时遍历两个链表，逐位计算它们的和。
2. 我们需要维护一个 进位。
3. 计算结果：
   • 当前位的值 = (两数之和 + 上一位的进位) % 10。
   • 新的进位 = Math.floor((两数之和 + 上一位的进位) / 10)。
4. 如果链表长度不一致，短链表缺失的位按 0 处理。
5. 当遍历完所有链表后，如果进位 carry 仍大于 0，需要在结果链表末尾额外添加一个节点。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    // 创建一个哑节点作为结果链表的头的前置节点，方便处理头节点
    const dummyHead = new ListNode(0);
    let current = dummyHead;
    let carry = 0; // 进位
    // 只要 l1 不为空，或者 l2 不为空，或者还有进位，就继续循环
    while (l1 !== null || l2 !== null || carry !== 0) {
        // 获取当前位的值，如果链表已遍历完则视为 0
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        // 计算当前位的和
        const sum = val1 + val2 + carry;
        
        // 更新进位
        carry = Math.floor(sum / 10);
        
        // 创建新节点存入当前位的计算结果 (取模 10)
        current.next = new ListNode(sum % 10);
        current = current.next;
        // 移动 l1 和 l2 指针
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    // 返回哑节点的下一个节点，即真正的头节点
    return dummyHead.next;
};

代码详解

1. 哑节点：我们使用了 dummyHead 节点。这在链表题中是一个常用技巧，它可以避免对头节点进行特殊的初始化判断，最后返回 dummyHead.next 即可。
2. 循环条件：while (l1 !== null || l2 !== null || carry !== 0)。
   • 这里之所以要加上 carry !== 0，是为了处理类似 [9, 9] + [1] 这种情况，最后会多产生一个进位节点 [0, 0, 1]。如果不判断进位，结果会丢失最高位的 1。
3. 取值逻辑：const val1 = l1 ? l1.val : 0;。使用三元运算符处理链表长度不一致的情况，短的链表遍历完后自动补 0 参与计算。

复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 分别为两个链表的长度。我们需要遍历较长的那个链表。
• 空间复杂度：O(max(m, n))，结果链表的长度最多为 max(m, n) + 1。