静奢之境

LongDz 的数字文墨提案

2. 两数相加

4 min

题目

2. 两数相加 中等

解法：模拟加法

思路

核心思想是模拟竖式加法，使用进位变量逐位计算。从最低位（链表头）开始同步遍历两链表，每位数相加后更新进位和当前位值。

正确性在于：逆序存储特性使链表头即为最低位，符合加法计算顺序；进位传递机制确保每位计算包含前一位的进位，且最终进位不会遗漏（循环条件包含进位非零）。数学上，每位计算满足：当前和 = 进位 + l1值 + l2值，新进位 = 当前和/10，当前位值 = 当前和%10，该过程等价于十进制加法原理。

  • Step 1: 创建哨兵节点dummy和当前指针curr，初始化进位carry=0
  • Step 2: 循环直到两链表为空且进位为0
  • Step 3: 计算当前和（含进位及两链表当前节点值）
  • Step 4: 更新进位carry=sum/10，创建新节点存储sum%10
  • Step 5: 移动curr指针及非空链表指针
  • Step 6: 返回dummy->next作为结果链表头

复杂度

  • 时间复杂度: O(max⁡(m,n))O(\max(m,n))，其中m,nm,n为两链表长度。瓶颈在遍历较长链表的每个节点。
  • 空间复杂度: O(max⁡(m,n))O(\max(m,n))，结果链表长度最大为max⁡(m,n)+1\max(m,n)+1（进位导致）。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0); // 哨兵节点
        ListNode* curr = dummy;
        int carry = 0;
        
        // 使用一个循环处理所有情况：l1非空、l2非空、或有进位
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0); // 哨兵节点
        ListNode* curr = dummy;
        int carry = 0;
        
        // 使用一个循环处理所有情况：l1非空、l2非空、或有进位
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
        }
        
        ListNode* ans = dummy->next;
        delete dummy; // 防止内存泄漏，虽然在 LeetCode 中不是严格必须的，但是个好习惯
        return ans;
    }
};
链表 模拟 LeetCode