Skip to main content

两数相加

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

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

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

示例 1：

image 输入：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. 逐位相加：同时遍历两个链表，从最低位（表头）开始逐位相加。
  2. 处理进位：每一位相加后可能产生进位（carry），需将进位传递到下一位。
  3. 处理长度不一致：若两个链表长度不同，短链表遍历完后，长链表剩余部分继续与进位相加。
  4. 处理最后进位：若遍历结束后仍有进位，需在结果链表末尾添加一个节点。

代码实现​

/**
 * 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}
 */
function addTwoNumbers(l1, l2) {
    const dummyHead = new ListNode(0); // 虚拟头节点，简化边界处理
    let current = dummyHead;           // 当前节点指针
    let carry = 0;                     // 进位值
    
    while (l1 || l2) {
        const x = l1 ? l1.val : 0;     // l1当前节点值（若为空则取0）
        const y = l2 ? l2.val : 0;     // l2当前节点值（若为空则取0）
        const sum = x + y + carry;     // 当前位的和（包含进位）
        
        carry = Math.floor(sum / 10);  // 计算新的进位
        current.next = new ListNode(sum % 10); // 创建当前位的节点
        current = current.next;        // 移动指针
        
        if (l1) l1 = l1.next;          // 移动l1指针
        if (l2) l2 = l2.next;          // 移动l2指针
    }
    
    // 处理最后可能的进位
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    
    return dummyHead.next; // 返回虚拟头节点的下一个节点（真正的头节点）
}

复杂度分析​

  • 时间复杂度：O(max(m, n))，其中 m 和 n 分别为两个链表的长度。
  • 空间复杂度：O(max(m, n))，主要用于存储结果链表。

示例验证​

输入：

  • l1: 2 → 4 → 3 （表示数字 342）
  • l2: 5 → 6 → 4 （表示数字 465）

输出：

  • 7 → 0 → 8 （表示数字 807，即 342 + 465 = 807）

过程：

  1. 个位相加：2 + 5 = 7，无进位。
  2. 十位相加：4 + 6 = 10，进位 1，当前位 0。
  3. 百位相加：3 + 4 + 1（进位）= 8，无进位。
  4. 结果链表：7 → 0 → 8。

关键细节说明​

  1. 虚拟头节点：使用虚拟头节点避免处理头节点的特殊情况，简化代码逻辑。
  2. 进位处理：每次相加后计算进位，并将其传递到下一位的计算中。
  3. 链表长度不一致：遍历过程中，若某个链表已遍历完，其对应的值取 0，确保另一个链表的剩余部分能继续与进位相加。