两数之和

算法简单哈希表约 514 字大约 2 分钟

题目描述

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

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

你可以假设除了数字 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]

提示

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

解题思路

1.模拟解法

实现代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  // 创建哑节点作为结果链表的起点
  const dummy = new ListNode();
  let current = dummy;
  let carry = 0; // 存储进位值

  // 当任意链表未遍历完或存在进位时继续循环
  while (l1 !== null || l2 !== null || carry > 0) {
    // 获取当前节点的值（已空节点视为0）
    const val1 = l1?.val ?? 0;
    const val2 = l2?.val ?? 0;

    // 计算当前位的总和及进位
    const sum = val1 + val2 + carry;
    const newVal = sum % 10;
    carry = Math.floor(sum / 10);

    // 创建新节点并移动指针
    current.next = new ListNode(newVal);
    current = current.next;

    // 移动原始链表指针（安全导航运算符避免空指针）
    l1 = l1?.next ?? null;
    l2 = l2?.next ?? null;
  }

  return dummy.next; // 返回结果链表的真正头节点
}

复杂度分析

⏰ 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
💾 空间复杂度：O(1)。注意返回值不计入空间复杂度。