LeetCode 2：两数相加（Add Two Numbers）链表进位从朴素到最优解
副标题 / 摘要 这题本质是把「小学竖式加法」搬到链表：同位相加、处理进位、走到末尾后可能还要补一个新节点。文章将从朴素思路推到最优单遍解法，并给出工程场景与多语言实现。 预计阅读时长：12~15 分钟 标签：链表、进位、模拟、LeetCode 2 SEO 关键词：Add Two Numbers, 两数相加, 逆序链表, 进位, LeetCode 2 元描述：用哨兵节点 + 单遍遍历在 O(max(m,n)) 时间完成两条逆序数字链表求和，附常见坑、工程应用和六语言代码。 目标读者 刚开始刷链表题，想建立稳定解题模板的同学 对「进位」和「边界处理」容易写错的中级开发者 希望把算法思维迁移到工程数据流处理的工程师 背景 / 动机 看似只是 LeetCode 入门题，但它练的能力非常实用： 多输入流同步推进（l1、l2 两个指针） 状态跨轮传播（carry 进位） 边界完整性（长度不同、最后一位进位） 这三点在工程里非常常见，例如金额分片累加、多源日志计数合并、流式统计补位等。 核心概念 逆序存储：个位在链表头部，十位在下一节点，以此类推 逐位相加：每轮只处理一个位，值来自 x + y + carry 进位传播：carry = sum // 10，当前位 digit = sum % 10 哨兵节点（dummy）：避免首次插入时区分“头节点是否为空” A — Algorithm（题目与算法） 题目重述 给你两个非空链表，表示两个非负整数。 数字按逆序存储，且每个节点存储一位数字。 请将两个数相加，并返回同样逆序存储的结果链表。 题目保证除数字 0 外，这两个数都不会以 0 开头。 输入输出描述 项目 含义 输入 两个链表 l1、l2，每个节点值在 0~9 输出 一个新链表，表示 l1 + l2 的结果（逆序） 示例 1 输入: l1 = [2,4,3], l2 = [5,6,4] 解释: 342 + 465 = 807 输出: [7,0,8] 示例 2 输入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 解释: 9999999 + 9999 = 10009998 输出: [8,9,9,9,0,0,0,1] 思路推导：从朴素到最优 朴素思路 1：先转整数再相加 把链表转成整数 n1、n2 做 n1 + n2 再把结果拆位转回链表 问题： ...