LeetCode2-两数相加

LeetCode 2 - 两数相加 是一道经典链表操作问题，经常作为面试中基础题的变体被考察。掌握多种解法及其变体，并熟悉其核心思路和模板代码，可以快速备战相关链表或大数计算问题。

---

题目描述

给定两个非空链表，它们代表两个非负整数，每个节点保存一个数字，数字按 逆序存储（个位在链表头部），求两个数的和并返回一个新的链表，表示其逆序和。

输入：两个链表，l1 表示整数 a，l2 表示整数 b。输出：表示结果 a + b 的链表。

示例:

输入: l1 = [2,4,3], l2 = [5,6,4] 输出: [7,0,8] 解释: 342 + 465 = 807

---

解法及其分析 解法 1：模拟加法（逐位相加） 思路 链表表示逆序存储的数字，相当于按从低位到高位逐位对齐相加，因此直接模拟两数加法过程： 遍历两个链表，从头到尾逐位相加，考虑进位。用 carry 表示当前进位值（初始为 0）。若链表长度不相等，可补 0，即看成空位处理。将每次相加后的结果（sum % 10）保存到新链表中。 完成遍历后，如果 carry 不为 0，则需要在结果链表末尾补 1。 模板代码 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); // 哑节点 ListNode p1 = l1, p2 = l2, current = dummyHead; int carry = 0; // 遍历两个链表 while (p1 != null || p2 != null) { int x = (p1 != null) ? p1.val : 0; // 当节点为空时看作 0 int y = (p2 != null) ? p2.val : 0; int sum = x + y + carry; // 当前位和 carry = sum / 10; // 计算进位 current.next = new ListNode(sum % 10); // 新节点保存当前位值 current = current.next; // 前进指针 if (p1 != null) p1 = p1.next; if (p2 != null) p2 = p2.next; } // 如果最后进位不为 0，添加额外节点 if (carry > 0) { current.next = new ListNode(carry); } return dummyHead.next; // 返回去掉哑节点后的结果链表 } } 复杂度分析 时间复杂度: O(max(m, n))，其中 m 和 n 是两个链表的长度，需遍历长链表的每个节点。空间复杂度: O(1)，除了结果链表外，没有使用额外空间。

---

解法 2：递归解法 思路 使用递归模拟逐位相加的过程： 每次处理一对链表节点，计算当前位的和以及进位。递归调用处理剩余链表部分，进位值通过函数参数传递。 递归本质就是逆序链表的“从尾到头”的回溯计算。 模板代码 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return helper(l1, l2, 0); } private ListNode helper(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null && carry == 0) { return null; // 递归结束条件 } int sum = carry; if (l1 != null) sum += l1.val; if (l2 != null) sum += l2.val; ListNode node = new ListNode(sum % 10); // 保存当前位 node.next = helper( (l1 != null) ? l1.next : null, (l2 != null) ? l2.next : null, sum / 10 // 进位传递到下一层递归 ); return node; } } 复杂度分析 时间复杂度: O(max(m, n))，需要递归处理每一位。空间复杂度: O(max(m, n))，递归调用栈的深度最大为链表长度。

---

解法 3：反转链表法（适用于顺序存储时） 核心问题

如果链表存储的是整数的正常顺序（高位在前），如何求两数和？

思路 若链表采用正序存储，则需要先将链表反转（采用常用 反转链表模板）。使用解法 1 的逐位相加方法，计算链表和。最后将结果链表反转，恢复顺序。 模板代码 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { l1 = reverseList(l1); l2 = reverseList(l2); ListNode result = addTwoNumbersReversed(l1, l2); return reverseList(result); } // 反转链表 private ListNode reverseList(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } // 借助解法1，计算反转链表的和 private ListNode addTwoNumbersReversed(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode current = dummyHead; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int x = (l1 != null) ? l1.val : 0; int y = (l2 != null) ? l2.val : 0; int sum = x + y + carry; current.next = new ListNode(sum % 10); carry = sum / 10; current = current.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return dummyHead.next; } } 复杂度分析 时间复杂度: O(m + n)，反转链表和加法操作总共需要线性时间。空间复杂度: O(1)，原地操作链表。

---

变体问题 1. 链表与整数数组转换 将链表转换为整数数组，再处理运算，最后将结果转换回链表。对于大整数字符串输入，也可以使用类似思路。 2. 两个数字是否相等 判断两个链表存储的整数是否相等。 3. 合并 k 个链表的和 扩展为 k 个链表相加，这可以使用优先队列或逐链表合并。 4. 大数相加（整数以字符串形式存储） 给定两个数字以字符串形式存储，模拟大数加法逻辑。和这道题的链表加法思路非常类似。 5. 减法模拟 如果要求两个链表表示的数相减，稍作修改： 按位模拟减法。借位处理时，考虑前一位减 1。

---

快速 AC 总结 熟记关键模块： 使用链表构造哑节点（dummyHead）。逐位相加时的循环结构与边界条件。进位处理逻辑（如 carry）。 应对变体问题： 若逆序时直接逐位相加，正序时先反转链表。若输入为整数数组或大数字符串，则手动模拟链表结构。 调试基础功能（链表遍历、构建和反转）： 熟悉链表的单步操作和空链表边界处理，无论变体或难度增加都可以高效应对。

通过练习核心模板和理解变体模式，可以轻松解决这类链表和数字计算相关的题目。