题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解法
1、模拟加法运算
- 初始化和链表
- 初始化l1、l2、头结点索引
- 初始化进位存储
- 遍历 l1、l2链表
- 获取 l1 当前节点的值 x
- 获取 l2 当前节点的值 y
- 执行相加：
carry + x + y - 更新进位值
- 将结果节点链接到结果链表中
- 更新指针到下一个节点
- 更新 l1、l2 节点到下一个节点
- 如果有进位，则需要增加一个节点
- 返回结果链表的头结点
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0); //新建一个空链表
ListNode p = l1, q = l2, curr = res;//得到两个加数的个位结点索引
int carry = 0; //进位存储
while (p != null || q != null) { //至少有一个数还没加完
int x = (p != null) ? p.val : 0; //l1已经没有结点了则为0
int y = (q != null) ? q.val : 0; //l2已经没有结点了则为0
int sum = carry + x + y; //求当前位的结果
carry = sum / 10; //更新进位
curr.next = new ListNode(sum % 10); //存储该位的结果
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return res.next;
}
递归实现
链表复用。
- 递归入参：l1、l2、进位
- 都到达链表尾部，处理进位值
l1 = null l2 = nullcarry != 0插入一个节点
l1 = null- l2 切换到 l1
- 求和
carry += l1.val + (l2 != null ? l2.val : 0); - 更新节点值：
l1.val = carry % 10; - 递归求解下一个节点，入参：
l1.next,l2.next,carry - 返回l1
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwo(l1, l2, 0);// 增加一个进位入参
}
// l1 和 l2 为当前遍历的节点，carry 为进位
private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null) { // 递归边界：l1 和 l2 都是空节点
return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
}
if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
l1 = l2;
l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
}
carry += l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起
l1.val = carry % 10; // l1.val的值已经没有用了，复用当前l1节点，保存求和结果
l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
return l1;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
