LeetCode 2 - 两数相加

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

题目描述

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

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

示例:

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

解法及其分析

解法 1：模拟加法（逐位相加）

思路

链表表示逆序存储的数字，相当于按从低位到高位逐位对齐相加，因此直接模拟两数加法过程：
1. 遍历两个链表，从头到尾逐位相加，考虑进位。
2. 用 carry 表示当前进位值（初始为 0）。
3. 若链表长度不相等，可补 0，即看成空位处理。
4. 将每次相加后的结果（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; // 当节点为空时看作 0int 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;}
}