仓颉语言实现 LeetCode 第 2 题「两数相加」：Option 模式匹配与链表进位迭代详解

示例工程教育【免费下载链接】Exercises本仓收集仓颉算法题解程序项目地址https://gitcode.com/Cangjie/Exercises点击查看免费下载本篇以 Exercises 仓库中的仓颉Cangjie题解 【Leetcode】2.两数相加/readme.md 为主线完整还原「用链表模拟两个非负整数相加」的解题思路与逐行源码剖析并结合仓颉特有的Option类型、if-let模式解构与??操作符帮助读者掌握在强类型、空安全语言中编写链表遍历类题解的完整实战方案。读完本文你应能独立用仓颉语言写出带进位传播的链表迭代算法并理解Option判空语法的真实语义。1. 题目与问题建模本题是 LeetCode 第 2 题「两数相加」Add Two Numbers。原题描述可在题目页面的官方链接readme 中给出的 leetcode.cn 题目链接此处按仓库规范不再重复外链中查看其核心规则为给定两个非空链表表示两个非负整数每个链表节点只存储一位数字且数字按逆序存储低位在链表头部假设两数都不含前导 0除数字 0 本身外将两个数相加以同样的逆序链表形式返回结果。逆序存储的设计使得链表头部恰好是低位天然契合「从低位到高位逐位相加、逐位进位」的十进制加法流程因此本题无需反转链表、无需整型转换用一次单向遍历即可完成。在 Exercises 仓库中该题解以独立子目录组织目录命名为「【Leetcode】2.两数相加」符合仓库根 README.md 中约定的提交规范每道编程题放在独立子目录、目录以题目命名并优先使用中文并在子目录放置readme.md填写题目描述与解题指导。目录内两个文件分工明确文件职责【Leetcode】2.两数相加/readme.md记录题目链接、解题思路、时间/空间复杂度与所用仓颉语法点【Leetcode】2.两数相加/n2.cj仓颉语言完整题解实现SolutionN2类共 41 行2. 解题思路三条件循环 逐位进位readme 中给出的核心思路原文为迭代两个 List只要满足l1不为 None、l2不为 None、进位不为 0 中条件之一就一直迭代 每次迭代sum l1 的值如果不为空 l2 的值如果不为空 进位。对应地源码 n2.cj#L24 中的循环条件写为while (l1cur.isSome() || l2cur.isSome() || carry ! 0) {这三个条件缺一不可逐条对应三类边界场景l1cur.isSome()l1 还有剩余位两链长度可能不等短链走完后长链仍需继续加l2cur.isSome()l2 还有剩余位carry ! 0两条链都耗尽后最高位可能仍有一次进位需要「额外追加一个节点」。例如 5 5 10链表遍历结束时carry仍为 1必须再多写一位。循环体内每一轮固定执行四步见 n2.cj#L25-L37sum初始化为carry上一轮的进位若 l1 当前节点存在则累加其val并把游标前移到node.next若 l2 当前节点存在做同样的累加与前移用整除与取模分离进位与当前位carry sum / 10、新节点值为sum % 10挂到结果链表尾部。3. 源码逐行剖析n2.cj以下是 n2.cj 的完整实现仅剔除头注释package cangjieLeetcode.n1_n100 import cangjieLeetcode.common.ListNode class SolutionN2 { func addTwoNumbers(l1: ?ListNode, l2: ?ListNode): ?ListNode { var t ListNode(0) var cur t var l1cur l1 var l2cur l2 var carry 0 while (l1cur.isSome() || l2cur.isSome() || carry ! 0) { var sum carry if(let Some(node) - l1cur) { sum node.val l1cur node.next } if(let Some(node) - l2cur) { sum node.val l2cur node.next } carry sum / 10 cur.next Some(ListNode(sum % 10)) cur cur.next??ListNode(0) } t.next } }3.1 哑头节点dummy head技巧第 19-20 行var t ListNode(0)、var cur t创建了值为 0 的哑头节点真正的结果节点从其next开始挂接。这样做的收益是结果链表始终非空无需对「第一个真实节点」做特判结束时直接返回t.next第 38 行天然剥离哑节点。由于返回值类型是?ListNode即OptionListNode且循环至少执行一次两个空链表输入不合法t.next在合法输入下必为Some因此可以直接作为Option返回。3.2if-let模式解构判空与取值的二合一第 26-33 行对两个游标分别使用了仓颉的if-let语法if(let Some(node) - l1cur) { sum node.val l1cur node.next }l1cur的类型是?ListNode可空类型。if(let Some(node) - l1cur)会在条件为真时把Option包裹的节点解构到局部变量node块内node即为非空的ListNode可直接访问node.val、node.next若游标已为None则整个if块被跳过。这避免了先isNone()判断、再手动取值的重复代码是仓颉处理可空类型的惯用写法。值得注意的是两个if块是独立的而非else if因为某轮循环中完全可能只有一条链还有剩余位两链长度不同必须各自独立判断、独立累加。3.3 进位与尾节点整除取模 ??兜底第 34-36 行carry sum / 10 cur.next Some(ListNode(sum % 10)) cur cur.next??ListNode(0)sum的取值范围是 0189 9 1 个进位故sum / 10只会得到 0 或 1sum % 10即当前位数字。这里利用了仓颉整型除法的整除语义每次循环都先给cur.next挂上新节点再把游标前移保证下一轮始终在结果链表尾部关于cur cur.next??ListNode(0)上一行刚执行过cur.next Some(...)因此从源码结构看cur.next在此处逻辑上必定是Some右侧的ListNode(0)兜底分支实际不会被构造——作者此处是在实践 readme 强调的??语法把「已知为 Some 的 Option」展开成值而非处理真实的空值分支。3.4 返回值循环结束后返回t.next。哑节点 0 被剔除若最后一轮产生了进位它已被第 3 个循环条件多跑一轮而追加为结果链表的最后一个节点如 999 1 的第三位 1。4. 仓颉语法点小结readme 的「仓颉语法」一节列出了本题涉及的两个知识点结合源码展开如下4.1Option的isSome()/isNone()?ListNode即OptionListNode可承载Some(node)或None两种状态。判断空值的谓词为isSome()/isNone()本题在while条件中连续使用了两个isSome()。4.2??操作符readme 原文描述Option类型的??语法a ?? b等同于if(a.isNone()){b} else {T}T 为 a 中包裹的值语义即左操作数为None时取右操作数作为默认值否则取出左操作数包裹的值。它等价于许多语言中的??nullish coalescing或 Swift/Kotlin 的??用法是提供兜底默认值最简练的写法。4.3 同系列题解中的关联用法同一包cangjieLeetcode.n1_n100下的其他题解展示了相近的 Option 用法可作交叉印证【Leetcode】1.两数之和/n1.cj 中if (let Some(x) - m.get(target - nums[i]))对HashMap.get的可空返回值做if-let解构与本题对链表游标的解构完全同构【Leetcode】3.无重复字符的最长子串/n3.cj 则展示了iterator()、enumerate()与扩展方法等其他仓颉特性。5. 一次完整的运行推演以经典样例l1 [2, 4, 3]表示 342、l2 [5, 6, 4]表示 465为例逐轮推演源码行为轮次进入时状态sum 计算新节点值 (sum % 10)carry出结果链尾节点1l1cur2, l2cur5, carry002577072l1cur4, l2cur6, carry004610017 - 03l1cur3, l2cur4, carry11348807 - 0 - 84l1curNone, l2curNone, carry0循环条件全部为假退出———返回t.next即7 - 0 - 8表示 807符合 342 465 807。再看进位溢出的边界样例l1 [9, 9, 9]、l2 [9, 9, 9, 9]前三轮分别得到 8/8/8 且 carry 恒为 1第四轮两条链中只剩 l2 的 9sum 1 9 10新节点 0、carry 仍为 1由于carry ! 0循环再跑第五轮sum 1追加节点 1 后 carry 归 0。最终结果为8 - 8 - 8 - 0 - 19999 999 10998恰好验证了第 2 节强调的第三个循环条件的必要性。6. 复杂度分析readme 给出的结论为时间 O(n)空间 O(1)。结合源码可以更精确地理解其口径时间设两链长度为 m、n循环轮数不超过max(m, n) 1多出的 1 轮用于消化最高位进位每轮 O(1)故时间复杂度为 O(max(m, n))即 readme 所述的 O(n)空间除输出结果链表本身外算法只使用cur、l1cur、l2cur、carry、sum等常数个变量辅助空间 O(1)。新建的结果节点是题目要求的返回值不计入辅助空间。7. 仓库内相关实现与阅读指引从源码结构看n2.cj顶部声明了package cangjieLeetcode.n1_n100并import cangjieLeetcode.common.ListNode而同目录的 n1、n3 题解共用同一个包名这说明本仓库中的 LeetCode 系列文件是按「同一外部工程模块」的约定组织的当前仓库内并未包含cangjieLeetcode.common包本身ListNode的定义不在本仓库提交范围内直接编译单个文件需要补上该公共依赖。如果想在仓库内寻找结构相近、可直接编译参考的ListNode实现可查看 算法思想解题合集/src/structures/listnode.cj它定义了带val: Int与next: ?ListNode None字段、多种构造器按值构造、按字符串1-5-3解析、按数组构造以及toString()打印链表的ListNode类其「字段 Option 型 next 便捷构造器」的设计与n2.cj所依赖的节点语义一致可作为理解链表节点建模的参考注意二者分属cj_algorithm.structures与cangjieLeetcode.common两个不同包并非同一类型。复现建议阅读本仓库时无需修改任何文件直接打开 n2.cj 对照本文第 3 节的逐行剖析即可若要在本地跑通建议按仓库根 README.md 的目录约定在具备仓颉开发环境含cjpm工具链的完整工程中添加cangjieLeetcode.common.ListNode公共定义再调用SolutionN2().addTwoNumbers(l1, l2)并打印返回链表验证第 5 节的推演结果。8. 小结本题的标准解法是哑头节点 双游标单向遍历循环条件l1cur.isSome() || l2cur.isSome() || carry ! 0完整覆盖了「长链剩余」「短链耗尽」「高位进位追加」三类边界仓颉侧的核心语言工具是Option判空isSome()/isNone()、if-let模式解构if(let Some(node) - opt)与??默认值操作符三者组合让空安全代码比显式判空写法更紧凑复杂度为时间 O(max(m, n))、辅助空间 O(1)是链表模拟题中「一次遍历、无回溯」的基准写法。赞分享示例工程教育【免费下载链接】Exercises本仓收集仓颉算法题解程序项目地址https://gitcode.com/Cangjie/Exercises点击查看免费下载相关推荐LeetCode 0002 Add Two Numbers 两数相加链表模拟竖式加法与进位传播实战解析含递归与迭代双解法LeetCode 0002 Add Two Numbers 两数相加链表模拟竖式加法与进位传播实战解析含递归与迭代双解法 本篇技术指南以 hints/ad示例工程教程AlgoNote 题解LeetCode 0002「两数相加」——逆序链表的竖式加法模拟与进位处理AlgoNote 题解LeetCode 0002「两数相加」——逆序链表的竖式加法模拟与进位处理 导读 本篇是「算法通关手册」AlgoNote 对 LeetC教程文档知识库LogicStack-LeetCode 题解精讲LeetCode 2. 两数相加——逆序链表竖式加法与哨兵技巧LogicStack LeetCode 题解精讲LeetCode 2. 两数相加——逆序链表竖式加法与哨兵技巧 本文是「刷穿 LeetCode」系列的第 2教程文档创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考