LeetCode 面试题 02.05. 链表求和

约 5 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 字节跳动 微软 美团 腾讯 百度 滴滴 小米 程序员面试金典（第 6 版）
标签
数学 链表 递归 加法问题
目录

题目描述

✅ 面试题 02.05. 链表求和

image-20230305200426605

题意分析

两个链表各自表示一个非负整数，每个节点存一位十进制数字，且数字是逆序存放的——链表头是个位，往后依次是十位、百位。要求返回两数之和，结果同样按逆序链表给出。

约束里最重要的信号是这个「逆序」。手算竖式加法的顺序恰恰是从个位往高位推进的，而逆序链表的遍历方向正好就是个位到高位，两者天然对齐，因此可以边遍历边输出，不需要先把链表翻转，也不需要栈来倒序。这与本题的进阶版（数字正序存放）形成对照，那种情况才必须借助翻转或栈。

边界有三处要提前想到。其一，两个链表长度可以不同，短的那个走完之后另一个还得继续走。其二，最高位相加可能产生新的进位，比如 99 + 1 = 100，结果链表会比两个输入都长一位。其三，题目允许数字为 0，即输入可能是单节点 [0]，此时不能返回空链表。另外无需担心整数溢出——全程只对单个数位做加法，最大值是 9 + 9 + 1 = 19。

解法：逐位相加模拟进位

核心思路

链表按低位到高位存储，遍历顺序恰好与竖式加法一致，不需要反转。也不能先转成整数再相加，因为链表长度没有整数类型的位数限制。

每轮把两个当前位（链表结束则视为 0）和进位 carry 相加。本位写入 sum % 10，下一位进位是 sum / 10。由于最大和为 9 + 9 + 1 = 19，进位始终只可能是 0 或 1。

循环不变量是：dummy.next 到 tail 已正确表示所有处理过的低位，l1、l2 指向下一对待处理数位，carry 保存低位向当前位产生的进位。每轮按竖式规则生成一位，不变量继续成立；当两个链表和进位都为空时，所有位恰好处理完毕。

解题步骤

  1. 用哑节点 dummy 统一结果链表首节点和后续节点的追加逻辑，tail 始终指向结果尾部。
  2. 当 l1、l2 或 carry 任一仍有效时继续循环；链表为空的一侧按 0 处理。
  3. 计算 sum，尾插值为 sum % 10 的节点，再令 carry = sum / 10。
  4. 两个非空输入指针各自后移，最后返回 dummy.next。

例如 [9, 9] + [1]：两轮分别得到 0、0，且都产生进位 1；输入耗尽后，循环因 carry = 1 再执行一次，补出最高位，结果为 [0, 0, 1]。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            // 当前节点保存个位，十位作为下一轮进位。
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }
        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    carry := 0

    for l1 != nil || l2 != nil || carry != 0 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        // 结果链表同样按逆序存储，直接尾插当前位。
        tail.Next = &ListNode{Val: sum % 10}
        tail = tail.Next
        carry = sum / 10
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(\max(m,n))$。每轮至少消费一个输入节点，最多再执行一轮处理最终进位。
  • 空间复杂度：$O(1)$ 额外空间；返回链表占 $O(\max(m,n))$ 空间。

关键点总结

  • 逆序存储使低位先到，正好可以一趟模拟竖式加法。
  • 循环条件必须覆盖两个输入和最终进位，长度不等也无需预处理。
  • sum % 10 是当前位，sum / 10 是下一位进位，两者必须来自同一个 sum。
  • 哑节点只负责简化尾插，真正结果从 dummy.next 开始。

易错点总结

  • 循环条件使用 &&：短链表结束时会丢掉长链表剩余高位。
  • 忽略最终进位：[5] + [5] 会错误得到 [0]，正确结果是 [0, 1]。
  • 把本位和进位写反：本位应取模 10，进位应整除 10。
  • 返回 dummy 而不是 dummy.next：答案会多出一个占位的前导节点。

相似题目

题目 难度 考察点
2. 两数相加 中等 与本题同型的原版，可直接对照两份题面确认逆序这一前提
43. 字符串相乘 中等 竖式乘法要开中间数组存各位乘积，还需处理前导零
66. 加一 简单 数组正序存放，需从末尾倒着推进位，全 9 时还要扩容
369. 给单链表加一 中等 单链表且高位在前，只加 1，可用哨兵定位最后一个非 9 的位置
415. 字符串相加 简单 载体换成字符串且高位在前，需双下标从尾向前并注意字符与数字的换算
445. 两数相加 II 中等 数字正序存放，必须靠栈或反转制造低位优先的处理顺序
LCR 025. 两数相加 II 中等 与 445 同型，可顺带练习头插法直接生成正序结果