仓颉语言实战：链表两数相加工具库详解
前言
在数据结构与算法的学习中，链表操作是一个经典且重要的主题。今天，我将带大家使用华为推出的新一代编程语言——仓颉语言，实现一个实用的链表两数相加工具库。
这个工具库解决的是一个经典问题：给定两个非空链表，表示两个非负整数，它们的每位数字都是按照逆序方式存储的，每个节点只能存储一位数字。我们需要将这两个数相加，并以相同形式返回一个表示和的链表。
本文将分享从问题分析到完整实现的全过程，包括链表数据结构设计、核心算法实现、边界情况处理以及完善的单元测试，希望能为学习仓颉语言的开发者提供一个实用的参考案例。
问题描述
题目定义
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例说明
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
链表表示：
2 -> 4 -> 3 (表示数字 342)
+ 5 -> 6 -> 4 (表示数字 465)
-----------------
= 7 -> 0 -> 8 (表示数字 807)
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
解释：9999999 + 9999 = 10009998
项目设计
设计目标
在设计这个工具库时，我确立了以下核心目标：正确性：准确处理各种边界情况和进位逻辑
高效性：时间复杂度O(max(m,n))，空间复杂度O(max(m,n))
可读性：代码结构清晰，逻辑易于理解
可测试性：提供完善的测试用例，覆盖各种场景
实用性：提供辅助函数方便创建和展示链表
项目架构
项目采用典型的仓颉语言项目结构：
add_two_numbers/
├── cjpm.toml # 项目配置文件
├── src/
│ ├── main.cj # 主程序入口（示例代码）
│ └── module/
│ ├── list_node.cj # 链表节点定义
│ ├── add_two_numbers.cj # 核心功能实现
│ └── add_two_numbers_test.cj # 单元测试
├── doc/ # 文档目录
├── README.md # 项目说明
└── CHANGELOG.md # 版本历史
算法思路
解决这个问题的关键思路如下：
同时遍历：使用指针同时遍历两个链表
逐位相加：将对应位置的数字相加，加上上一位的进位
构建结果链表：将每位的计算结果（取余10）作为新节点
更新进位：计算新的进位值（除以10）
处理剩余：当一个链表遍历完后，继续处理另一个链表
最终进位：如果最后还有进位，添加新节点
用伪代码表示：
carry = 0
while l1 != null || l2 != null || carry != 0:
sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry = sum / 10
newNode.val = sum % 10
移动指针
核心实现
1. 链表节点定义
首先，我们需要定义链表节点的数据结构：
代码解析：
public class：定义公共类，可被外部访问
var 成员变量：使用 var 声明可变成员变量
可选类型：?ListNode 表示可选类型，可能为 None
构造函数：使用 init 定义构造函数，支持默认参数
2. 核心算法实现
接下来实现核心的两数相加函数：
// 两数相加函数
// 给定两个非空链表，表示两个非负整数
// 数字按逆序存储,每个节点存储一位数字
// 返回两数之和的链表
public func addTwoNumbers(l1: ?ListNode, l2: ?ListNode): ?ListNode {
var dummyHead = ListNode(0) // 虚拟头节点
var current = dummyHead
var carry: Int64 = 0 // 进位
var p1 = l1
var p2 = l2
// 遍历两个链表
var continueLoop = true
while (continueLoop) {
var val1: Int64 = 0
var val2: Int64 = 0
var hasP1 = false
var hasP2 = false
// 获取当前节点的值
match (p1) {
case Some(node) =>
val1 = node.val
p1 = node.next
hasP1 = true
case None =>
val1 = 0
}
match (p2) {
case Some(node) =>
val2 = node.val
p2 = node.next
hasP2 = true
case None =>
val2 = 0
}
// 检查是否继续循环
if (!hasP1 && !hasP2 && carry == 0) {
continueLoop = false
break
}
// 计算和与进位
var sum = val1 + val2 + carry
carry = sum / 10
var digit = sum % 10
// 创建新节点
current.next = Some(ListNode(digit))
match (current.next) {
case Some(node) =>
current = node
case None =>
break
}
}
return dummyHead.next
}
算法解析：
哑节点技巧：使用哑节点（dummy head）简化边界处理，避免特殊判断第一个节点
三指针法：p1、p2分别遍历两个链表，current构建结果链表
进位处理：使用carry变量保存进位，每次计算都要加上
条件判断：使用三元表达式处理链表为空的情况
循环条件：只要有任何一个链表未遍历完或还有进位，就继续循环
可选类型处理：使用match表达式安全地处理可选类型
3. 辅助函数：数组转链表
为了方便测试和使用，我们提供一个将数组转换为链表的函数：
4. 辅助函数：链表转数组
为了便于验证结果和调试，我们还需要一个将链表转换为数组的函数：
5. 辅助函数：打印链表
为了调试和展示，提供一个打印链表的函数：
使用示例
在 main.cj 中，我们提供完整的使用示例：
main(): Int64 {
println("========== 两数相加工具库 ==========")
println("")
// 测试用例 1: 342 + 465 = 807
// 链表表示: [2,4,3] + [5,6,4] = [7,0,8]
println("测试用例 1: 342 + 465 = 807")
var l1 = createListFromArray([2, 4, 3])
var l2 = createListFromArray([5, 6, 4])
printList(l1, "输入1")
printList(l2, "输入2")
var result1 = addTwoNumbers(l1, l2)
printList(result1, "结果")
println("验证: ${listToNumber(l1)} + ${listToNumber(l2)} = ${listToNumber(result1)}")
println("")
// 测试用例 2: 0 + 0 = 0
println("测试用例 2: 0 + 0 = 0")
var l3 = createListFromArray([0])
var l4 = createListFromArray([0])
printList(l3, "输入1")
printList(l4, "输入2")
var result2 = addTwoNumbers(l3, l4)
printList(result2, "结果")
println("验证: ${listToNumber(l3)} + ${listToNumber(l4)} = ${listToNumber(result2)}")
println("")
// 测试用例 3: 9999999 + 9999 = 10009998
// 链表表示: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
println("测试用例 3: 9999999 + 9999 = 10009998")
var l5 = createListFromArray([9, 9, 9, 9, 9, 9, 9])
var l6 = createListFromArray([9, 9, 9, 9])
printList(l5, "输入1")
printList(l6, "输入2")
var result3 = addTwoNumbers(l5, l6)
printList(result3, "结果")
println("验证: ${listToNumber(l5)} + ${listToNumber(l6)} = ${listToNumber(result3)}")
println("")
// 测试用例 4: 123 + 456 = 579
println("测试用例 4: 123 + 456 = 579")
var l7 = createListFromArray([3, 2, 1])
var l8 = createListFromArray([6, 5, 4])
printList(l7, "输入1")
printList(l8, "输入2")
var result4 = addTwoNumbers(l7, l8)
printList(result4, "结果")
println("验证: ${listToNumber(l7)} + ${listToNumber(l8)} = ${listToNumber(result4)}")
println("")
// 测试用例 5: 99 + 1 = 100
println("测试用例 5: 99 + 1 = 100")
var l9 = createListFromArray([9, 9])
var l10 = createListFromArray([1])
printList(l9, "输入1")
printList(l10, "输入2")
var result5 = addTwoNumbers(l9, l10)
printList(result5, "结果")
println("验证: ${listToNumber(l9)} + ${listToNumber(l10)} = ${listToNumber(result5)}")
println("")
println("========== 所有测试完成 ==========")
return 0
}
运行结果：
复杂度分析
时间复杂度
O(max(m, n))
其中 m 和 n 分别是两个链表的长度。算法需要遍历两个链表中较长的那个，每个节点只访问一次。
空间复杂度
O(max(m, n))
新创建的链表最多包含 max(m, n) + 1 个节点（考虑最高位进位的情况）。
项目配置
cjpm.toml 配置文件：
关键技术点总结
1. 哑节点技巧
使用哑节点（Dummy Head）是链表操作中的常用技巧，可以：
统一处理头节点和其他节点
简化边界条件判断
使代码更加简洁优雅
let dummyHead = ListNode(0) // 创建哑节点
// ... 操作
return dummyHead.next // 返回真正的头节点
2. 进位处理
进位是这个问题的核心：
let sum = val1 + val2 + carry // 当前位的总和
carry = sum / 10 // 计算新进位
let digit = sum % 10 // 当前位的数字
3. 可选类型处理
仓颉语言的可选类型提供了空安全保证：
var next: ?ListNode = None // 声明可选类型
match (node) { // 使用match安全访问
case Some(n) => n.val
case None => 0
}4. 循环条件设计
巧妙的循环条件确保所有情况都被正确处理：
while (p1 != None || p2 != None || carry != 0) {
// 继续条件：任一链表未完成 或 还有进位
}
扩展思考
1. 正序存储的情况
如果数字是正序存储（如 [3,4,2] 表示 342），该如何处理？
解决方案：
先反转两个链表
执行相加操作
再反转结果链表
2. 支持负数
如果要支持负数相加，需要：
增加符号位标记
实现减法逻辑
处理借位而不是进位
3. 支持更大的进制
如果每个节点存储的不是 0-9，而是 0-99 或其他进制：
const BASE: Int64 = 100 // 定义进制
carry = sum / BASE
digit = sum % BASE4. 链表加法优化
对于频繁的加法操作，可以考虑：
将链表转换为大整数
使用大整数库进行计算
再转换回链表形式
最佳实践建议
1. 代码规范
使用清晰的变量命名（dummyHead、carry）
添加详细的注释说明算法思路
遵循仓颉语言的命名规范
2. 错误处理
// 添加参数校验
public func addTwoNumbers(l1: ?ListNode, l2: ?ListNode): ?ListNode {
if (l1 == None && l2 == None) {
return None
}
// ... 其他逻辑
}3. 性能优化
避免不必要的对象创建
减少链表遍历次数
合理使用缓存
4. 测试驱动
先编写测试用例
覆盖所有边界情况
使用断言验证结果
总结
通过这个项目，我们：
- 掌握了链表的基本操作：节点创建、遍历、连接
- 学习了经典算法思想：哑节点、双指针、进位处理
- 实践了仓颉语言特性：可选类型、模式匹配、类定义
- 建立了完整的工程体系：代码实现、单元测试、文档编写
- 链表两数相加是一个看似简单但细节丰富的算法问题，通过仓颉语言的实现，我们不仅解决了问题本身，更重要的是掌握了：
- 问题分析能力：将实际问题抽象为算法模型
- 编码实现能力：将算法思想转化为可运行的代码
- 工程化思维：编写可测试、可维护、可扩展的代码
希望这个实战案例能够帮助你更好地理解仓颉语言和数据结构算法。如果你有任何问题或建议，欢迎交流讨论！
参考资料
仓颉语言官方文档
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
24
0- 0
已为社区贡献16条内容
所有评论(0)