两数相加 - Stellar Observer Protocol

640 字

3 分钟

两数相加

2025-08-20

Algorithms

递归

/

数学

/

链表

题目描述#

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

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

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

解题思路#

链表顺序特性：
- 数字逆序存储，头节点为最低位
- 直接对齐相加无需反转链表
模拟竖式加法：
- 同步遍历两个链表节点
- 计算当前节点和（包含进位）
进位处理：
- 当前位 = 和 % 10
- 进位 = Math.floor(和 / 10)
链表构造：
- 动态创建结果链表节点
- 处理链表长度不一致情况
边界处理：
- 最后进位需额外创建节点
- 处理空链表输入场景

关键洞察#

逆序存储优势：
- 天然符合加法运算方向（个位→高位）
- 避免链表反转操作
进位传递机制：
- 进位作为全局状态传递
- 最高位进位需特殊处理
等长处理优化：
- 短链表自动补零继续运算
- 避免额外条件判断
哑节点技巧：
- 使用哨兵节点简化头节点处理
- 结果链表无需特殊初始化

复杂度分析#

指标	说明
时间复杂度	O(max(m,n))：遍历较长链表长度
空间复杂度	O(max(m,n))：存储结果链表（可能多1节点）

代码实现#

1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val, next) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.next = (next===undefined ? null : next)
6
 * }
7
 */
8
/**
9
 * @param {ListNode} l1
10
 * @param {ListNode} l2
11
 * @return {ListNode}
12
 */
13
var addTwoNumbers = function (l1, l2) {
14
    const dummy = new ListNode();
15
    let temp = dummy;
16
    let carry = 0;
17
    while (l1 || l2 || carry) {
18
        const num1 = l1 ? l1.val : 0;
19
        const num2 = l2 ? l2.val : 0;
20
        const sum = num1 + num2 + carry;
21
        carry = sum >= 10 ? 1 : 0;
22
        temp.next = new ListNode(sum % 10);
23
        temp = temp.next;
24
        if (l1) l1 = l1.next;
25
        if (l2) l2 = l2.next;
26
    }
27
    return dummy.next;
28
};