LeetCode 2. 两数相加｜链表模拟+高精度加法（超详细图解版）

LeetCode 2. 两数相加链表模拟高精度加法超详细版题目描述给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例解析示例 1输入l1 [2,4,3]l2 [5,6,4]输出[7,0,8]核心解析链表逆序存储l1 对应整数 342l2 对应整数 465342 465 807逆序后即为 [7,0,8]。示例 2输入l1 [0]l2 [0]输出[0]核心解析两个单节点链表均为0相加结果仍为0符合“非负整数、无前置零”要求。示例 3输入l1 [9,9,9,9,9,9,9]l2 [9,9,9,9]输出[8,9,9,9,0,0,0,1]核心解析l1 对应 9999999l2 对应 9999求和为 10009998逆序后即为结果重点体现“进位贯穿全链路”场景。提示补充贴合题目实用提醒链表节点数范围 [1, 100]避免极端空链表题目明确非空但需处理两链表长度不一致场景。节点值范围 [0,9]符合“每位仅存一位数字”要求无需处理非数字节点。题目保证无前置零除数字0外无需额外判断结果链表的前置零问题。解题思路核心突破贴合面试视角本题核心是模拟人工竖式加法结合链表逆序存储的特性完美匹配竖式加法“从低位到高位”的计算逻辑也是链表操作的经典入门场景解题关键在于4点必掌握逆序存储的优势链表头节点对应数字的个位无需反转链表直接从个位开始相加贴合竖式加法逻辑简化计算流程。进位carry的维护每一位相加后若和大于等于10需向高位进1carry1否则carry0进位需贯穿整个计算过程包括最后一位相加后仍有进位的情况。链表长度不一致的处理当一个链表遍历完毕另一个仍有剩余节点时剩余节点可视为“与0相加”继续计算无需提前终止循环。结果链表的构建使用虚拟头节点dummy node统一处理头节点创建逻辑避免单独判断结果链表是否为空简化代码、降低出错率。算法步骤分步拆解可直接套用创建虚拟头节点dummy值任意仅用于占位定义指针curr指向 dummy用于构建结果链表。初始化进位carry 0初始无进位。循环条件while l1 or l2 or carry只要有一个链表未遍历完或仍有进位就继续计算。取值分别取出 l1、l2 当前节点的值若链表已遍历完取 0空节点补0。求和当前位总和 l1当前值 l2当前值 上一位进位 carry。更新当前位结果 总和 % 10取个位新进位 总和 // 10取十位仅0或1。构建结果新建节点值为当前位结果接入 curr.next然后 curr 指针后移。移动指针l1、l2 若未遍历完分别向后移动一位。循环结束后返回 dummy.next虚拟头节点的下一个节点即结果链表的真实头节点。辅助以示例1l1[2,4,3]l2[5,6,4]为例分步计算过程初始状态dummy [0]curr dummycarry0l1指向2l2指向5。第1次循环个位2507 → 当前位7carry0 → curr.next[7]curr后移l1指向4l2指向6。第2次循环十位46010 → 当前位0carry1 → curr.next[0]curr后移l1指向3l2指向4。第3次循环百位3418 → 当前位8carry0 → curr.next[8]curr后移l1、l2均为空。循环结束返回 dummy.next → [7,0,8]与示例输出一致。完整AC代码严格贴合题目要求可直接提交LeetCode 2 两数相加 完整AC代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next from typing import Optional class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: # 虚拟头节点统一头节点创建逻辑避免判断结果链表是否为空 dummy ListNode(0) curr dummy # 用于构建结果链表的指针 carry 0 # 存储进位初始为0无进位 # 循环条件链表未遍历完 或 仍有进位确保不遗漏任何一位 while l1 or l2 or carry: # 空节点补0避免空指针异常适配两链表长度不一致场景 val1 l1.val if l1 else 0 val2 l2.val if l2 else 0 # 计算当前位总和数值和 上一位进位 total val1 val2 carry carry total // 10 # 更新进位仅0或1 new_val total % 10 # 当前位结果取个位 # 新建节点接入结果链表指针后移 curr.next ListNode(new_val) curr curr.next # 原链表指针后移仅当链表未遍历完时 if l1: l1 l1.next if l2: l2 l2.next # 返回结果链表的真实头节点虚拟头节点的下一个节点 return dummy.next代码逐行解析通俗易懂兼顾新手与进阶虚拟头节点 dummy创建dummy ListNode(0)核心作用是“统一头节点逻辑”。若不使用虚拟头节点需单独判断结果链表是否为空再创建头节点代码冗余且易出错使用虚拟头节点后直接通过curr.next构建链表最后返回dummy.next即可。进位 carry初始值为0用于存储上一位相加产生的进位。由于每个节点值仅为0-9两个节点相加最大为9918加上进位1最大为19因此 carry 只能是0或1无需考虑更大的进位值。while l1 or l2 or carry**循环条件 **这是本题的核心细节也是新手最易出错的地方l1 or l2处理两链表长度不一致的情况如示例3l2先遍历完l1仍有节点。or carry处理最后一位相加后仍有进位的情况如9999991998最后一位进位1需额外添加节点1。val1 l1.val if l1 else 0**空节点补0 **当一个链表遍历完毕指针为None其后续节点可视为“0”避免空指针异常同时符合竖式加法“位数不足补0”的逻辑。当前位与进位计算total val1 val2 carry计算当前位的总和包含上一位进位。carry total // 10取总和的十位作为新的进位0或1。new_val total % 10取总和的个位作为当前节点的值。结果链表构建每次新建一个节点值为new_val接入curr.next然后将 curr 指针后移确保后续节点能正常接入逐步构建完整的结果链表。原链表指针移动仅当 l1、l2 未遍历完指针不为None时才向后移动避免空指针异常适配所有长度场景。复杂度分析时间复杂度O ( m a x ( m , n ) ) O(max(m, n))O(max(m,n))其中 m、n 分别为 l1、l2 的节点数。解析循环次数取决于两个链表中较长的一个每个节点仅被访问一次无多余操作时间复杂度与节点总数线性相关效率最优。空间复杂度O ( m a x ( m , n ) ) O(max(m, n))O(max(m,n))最坏情况O ( m a x ( m , n ) 1 ) O(max(m, n) 1)O(max(m,n)1)。解析结果链表的长度最多为较长链表的长度 1如示例3进位导致多一个节点额外空间仅用于存储结果链表无其他冗余空间占用。补充若允许修改原链表可将空间复杂度优化至O ( 1 ) O(1)O(1)但会破坏原链表结构实际开发中不推荐面试中可作为优化思路提及。测试示例可本地运行快速验证补充链表构建、打印辅助函数复制可直接本地运行验证所有示例方便调试和理解本地测试辅助代码示例验证# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next from typing import Optional # 辅助函数1根据列表构建逆序链表贴合题目输入格式 def build_linked_list(arr): dummy ListNode(0) curr dummy for val in arr: curr.next ListNode(val) curr curr.next return dummy.next # 辅助函数2打印链表直观查看结果 def print_linked_list(head): res [] while head: res.append(str(head.val)) head head.next return -.join(res) # 本题AC代码复制上面的完整代码即可 class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) curr dummy carry 0 while l1 or l2 or carry: val1 l1.val if l1 else 0 val2 l2.val if l2 else 0 total val1 val2 carry carry total // 10 new_val total % 10 curr.next ListNode(new_val) curr curr.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next # 测试示例1 l1 build_linked_list([2,4,3]) l2 build_linked_list([5,6,4]) res1 Solution().addTwoNumbers(l1, l2) print(示例1输出, print_linked_list(res1)) # 输出7-0-8 # 测试示例2 l1 build_linked_list([0]) l2 build_linked_list([0]) res2 Solution().addTwoNumbers(l1, l2) print(示例2输出, print_linked_list(res2)) # 输出0 # 测试示例3 l1 build_linked_list([9,9,9,9,9,9,9]) l2 build_linked_list([9,9,9,9]) res3 Solution().addTwoNumbers(l1, l2) print(示例3输出, print_linked_list(res3)) # 输出8-9-9-9-0-0-0-1常见易错点避坑指南易错点1循环条件遗漏 carry导致最后一位进位未处理如999999最后进位1未添加节点1。易错点2空节点未补0直接访问 l1.val 或 l2.val导致空指针异常如l2先遍历完仍访问 l2.val。易错点3移动原链表指针时未判断链表是否为空如l1已为None仍执行 l1 l1.next。易错点4忘记移动 curr 指针导致结果链表仅存在一个节点死循环或链表断裂。避坑技巧牢记“循环条件三要素l1、l2、carry”“空节点补0”“指针必移动”可在代码中添加注释提醒自己。进阶延伸本题是链表高精度加法的基础题掌握后可延伸解决以下同类题目解题思路可直接复用LeetCode 445. 两数相加 II链表正序存储需先反转链表再按本题思路计算最后反转结果。LeetCode 67. 二进制求和字符串模拟二进制加法逻辑与本题一致维护进位、逐位相加。LeetCode 415. 字符串相加字符串模拟十进制加法本质与本题相同仅存储载体从链表改为字符串。总结本题作为 LeetCode 入门经典题核心考察链表操作和竖式加法模拟难度适中但细节较多是新手掌握链表和高精度计算的绝佳案例。解题核心记住3点① 用虚拟头节点简化链表构建② 用carry维护进位贯穿全流程③ 空节点补0处理链表长度不一致。代码逻辑清晰、可直接提交AC测试用例完整易错点和进阶延伸完善适合新手入门练习也可作为面试复习的基础题型。掌握本题后可轻松应对同类高精度加法问题提升链表操作能力。