题目描述
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
核心思路:数学模拟
这道题的本质是模拟手动加法运算。由于链表已经是逆序存储(个位在头),我们直接按顺序遍历并相加即可,不需要额外反转链表。
1. 关键变量
- **进位 (carry)**:相加结果大于等于 10 时,需要将
1 传递到下一位。
- **虚拟头节点 (dummyHead)**:用于简化链表的构建逻辑,最后返回
dummyHead.next。
- 双指针同步遍历:同时推移两个链表的指针。
2. 边界处理
- 长度不等:当其中一个链表遍历结束时,其值视为
0。
- 最终进位:如果最高位相加后产生进位(如 5 + 5 = 10),需在链表末尾新增一个值为
1 的节点。
代码实现
注意:我们将常见的 `val` 命名修改为 nodeValue,以避免与 Kotlin 关键字冲突并提高代码可读性。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
class ListNode(var nodeValue: Int) { var next: ListNode? = null }
class Solution { fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? { val dummyHead = ListNode(0) var tail = dummyHead var carry = 0 var p1 = l1 var p2 = l2
while (p1 != null || p2 != null || carry != 0) { val digit1 = p1?.nodeValue ?: 0 val digit2 = p2?.nodeValue ?: 0 val totalSum = digit1 + digit2 + carry carry = totalSum / 10 tail.next = ListNode(totalSum % 10) tail = tail.next!! p1 = p1?.next p2 = p2?.next }
return dummyHead.next } }
|
复杂度分析
- 时间复杂度:$O(\max(m, n))$。其中 $m$ 和 $n$ 分别为两个链表的节点数。我们需要完整遍历较长的那个链表。
- 空间复杂度:$O(1)$。除了用于存储答案的链表外,我们只使用了常数级别的额外空间(进位变量、临时指针等)。
技巧总结
- **虚拟头节点 (Dummy Head)**:链表题“必备神器”。它消除了对“头节点是否为空”的特殊处理逻辑。
- 逻辑合并:将
while 循环条件设为 p1 != null || p2 != null || carry != 0,可以一次性处理完所有计算,包括最后一位产生的额外进位。
- 命名优化:在 Kotlin 中,LeetCode 默认的
`val` 属性由于是关键字,必须加反引号,可读性极差。将其改名为 nodeValue 或 value 是更符合现代工程实践的做法。