跳到主要内容

两数相加

· 阅读需 5 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——2题​

💡 参考代码：​

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 将两个逆序存储的数字链表相加，返回表示和的链表
 * 
 * @param l1 第一个数字链表（逆序存储）
 * @param l2 第二个数字链表（逆序存储）
 * @return 表示两数之和的链表（逆序存储）
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // 创建虚拟头节点，简化链表操作
    struct ListNode dummyHead = {0};
    struct ListNode* current = &dummyHead;
    
    // 进位标志，初始为0
    int carry = 0;
    
    // 当l1或l2还有节点，或者还有进位时继续循环
    while (l1 != NULL || l2 != NULL || carry != 0) {
        // 获取当前位的数字，如果链表已遍历完则为0
        int x = (l1 != NULL) ? l1->val : 0;
        int y = (l2 != NULL) ? l2->val : 0;
        
        // 计算当前位的和
        int sum = x + y + carry;
        
        // 更新进位值
        carry = sum / 10;
        
        // 创建新节点存储当前位的结果（sum % 10）
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current->next->val = sum % 10;
        current->next->next = NULL;
        
        // 移动到新节点
        current = current->next;
        
        // 如果链表还未遍历完，移动到下一个节点
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    
    // 返回结果链表的头节点（跳过虚拟头节点）
    return dummyHead.next;
}

📖 总结：​

点击展开题目总结

🤔 两数相加

1️⃣ 题目核心信息​

🎯 功能描述：将两个逆序存储的非负整数链表相加，返回表示和的链表

📥 输入输出：

  • 输入：
    • l1: 第一个数字链表（逆序存储，每个节点存储一位数字）
    • l2: 第二个数字链表（逆序存储，每个节点存储一位数字）
  • 输出：表示两数之和的链表（同样逆序存储）

2️⃣ 实现原理​

💡 核心思路：模拟手工加法过程，从低位到高位逐位相加，处理进位

📋 实现步骤：

  1. 使用虚拟头节点简化链表操作
  2. 同时遍历两个链表，逐位相加
  3. 处理进位：当前位和大于等于10时需要进位
  4. 当两个链表都遍历完后，检查是否还有进位需要处理

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用虚拟头节点(dummyHead)简化链表构建过程
  • 统一处理不同长度链表：当一个链表遍历完时，将其值视为0
  • 进位处理：使用整除和取模运算分别获取进位和当前位值
  • 内存管理：动态分配新节点内存

4️⃣ 使用场景​

✅ 适用情况：​

  • 大数加法运算（超出基本数据类型范围的整数）
  • 链表操作练习
  • 模拟运算实现

⚠️ 前提条件：​

  • 链表非空且表示非负整数
  • 数字按逆序方式存储（低位在前）
  • 除了数字0外，其他数字不含前导零

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(max(m,n))，其中m和n分别是两个链表的长度，需要遍历较长的链表
  • 💾 空间复杂度：O(max(m,n))，结果链表的空间开销，最坏情况下需要max(m,n)+1个节点

6️⃣ 注意事项​

🚩 边界情况：​

  • 两个链表长度不同
  • 最后一位相加产生进位（如示例3）
  • 其中一个链表为空（题目保证非空）

💥 易错点：​

  • 忘记处理最后的进位
  • 没有正确处理不同长度链表的情况
  • 链表指针操作错误导致内存泄漏或空指针异常

7️⃣ 补充说明​

📌 示例详解：l1 = [2,4,3], l2 = [5,6,4]​

我们来逐步跟踪 addTwoNumbers(l1, l2) 的执行过程：

初始状态：​

  • l1: 2 → 4 → 3 → NULL (表示数字342)
  • l2: 5 → 6 → 4 → NULL (表示数字465)
  • dummyHead: 虚拟头节点
  • current: 指向 dummyHead
  • carry: 0 (初始进位)

第1步迭代：​

  • x = l1->val = 2, y = l2->val = 5
  • sum = x + y + carry = 2 + 5 + 0 = 7
  • carry = sum / 10 = 7 / 10 = 0
  • 创建新节点：current->next = new_node(7)
  • 更新指针：
    • current = current->next (指向值为7的节点)
    • l1 = l1->next (指向值为4的节点)
    • l2 = l2->next (指向值为6的节点)

当前结果链表：dummyHead → 7

第2步迭代：​

  • x = l1->val = 4, y = l2->val = 6
  • sum = x + y + carry = 4 + 6 + 0 = 10
  • carry = sum / 10 = 10 / 10 = 1
  • 创建新节点：current->next = new_node(0)
  • 更新指针：
    • current = current->next (指向值为0的节点)
    • l1 = l1->next (指向值为3的节点)
    • l2 = l2->next (指向值为4的节点)

当前结果链表：dummyHead → 7 → 0

第3步迭代：​

  • x = l1->val = 3, y = l2->val = 4
  • sum = x + y + carry = 3 + 4 + 1 = 8
  • carry = sum / 10 = 8 / 10 = 0
  • 创建新节点：current->next = new_node(8)
  • 更新指针：
    • current = current->next (指向值为8的节点)
    • l1 = l1->next (NULL)
    • l2 = l2->next (NULL)

当前结果链表：dummyHead → 7 → 0 → 8

结束条件：​

  • l1 == NULL, l2 == NULL, carry == 0
  • 循环结束

返回结果：​

  • 返回 dummyHead.next，即链表 7 → 0 → 8
  • 这表示数字807，确实是342+465的结果

通过这个例子，我们可以看到算法正确地模拟了手工加法过程，从低位到高位逐位计算，并正确处理了进位情况。

加载评论中...