2. 两数相加

0 - 算法, 0.1 - 算法题目, 0.1.0 - 简单 本文总阅读量次

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 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? {
        // 创建虚拟头节点，其 next 存储真正的结果
        val dummyHead = ListNode(0)
        var tail = dummyHead
        
        // 进位标识
        var carry = 0
        
        // 两个链表的遍历指针
        var p1 = l1
        var p2 = l2

        // 只要还有节点未处理，或还有进位需要结算，就继续循环
        while (p1 != null || p2 != null || carry != 0) {
            // 取出当前位的值，若已空则取 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)$。除了用于存储答案的链表外，我们只使用了常数级别的额外空间（进位变量、临时指针等）。

技巧总结

  1. **虚拟头节点 (Dummy Head)**：链表题“必备神器”。它消除了对“头节点是否为空”的特殊处理逻辑。
  2. 逻辑合并：将 while 循环条件设为 p1 != null || p2 != null || carry != 0，可以一次性处理完所有计算，包括最后一位产生的额外进位。
  3. 命名优化：在 Kotlin 中，LeetCode 默认的 `val` 属性由于是关键字，必须加反引号，可读性极差。将其改名为 nodeValue 或 value 是更符合现代工程实践的做法。
0 - 算法, 0.1 - 算法题目, 0.1.0 - 简单