算法训练营第一期 | 两数相加 II
一、题目描述
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
二、题目解析
三、参考代码
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 构建两个栈，用来储存两个链表中的元素
// stack1 用来存储链表 l1 中的元素
Stack<Integer> stack1 = new Stack<Integer>();
// stack2 用来存储链表 l2 中的元素
Stack<Integer> stack2 = new Stack<Integer>();
// 依次把链表 l1 中的元素加入到 stack1 中
while (l1 != null) {
// 把当前节点加入到 stack1 中
stack1.push(l1.val);
// 继续向后遍历
l1 = l1.next;
}
// 依次把链表 l2 中的元素加入到 stack2 中
while (l2 != null) {
// 把当前节点加入到 stack2 中
stack2.push(l2.val);
// 继续向后遍历
l2 = l2.next;
}
// 设置一个进位，初始化为 0
// 两个个位数相加，进位只能是 1 或者 0
// 比如 7 + 8 = 15，进位是 1
// 比如 2 + 3 = 6，没有进位，或者说进位是 0
int carryBit = 0;
// 构建一个链表用来存放 l1 和 l2 两个链表相加的结果
// 其中 dummy 这个节点为虚拟头结点
ListNode dummy = new ListNode(-1);
// 只要任意一个栈或者 carryBit 有值，那么就需要求和
while (!stack1.isEmpty() || !stack2.isEmpty() || carryBit != 0) {
// 三目运算符，如果栈为空，就用 0 来占位，否则使用栈顶元素值
// 获取 stack1 的栈顶元素值
int x = stack1.isEmpty() ? 0 : stack1.pop();
// 获取 stack2 的栈顶元素值
int y = stack2.isEmpty() ? 0 : stack2.pop();
// 每一位计算的同时需要考虑上一位的进位情况
int sum = x + y + carryBit;
// 获取当前计算结果的十位数
// 比如 7 + 8 = 15
// 那么 sum / 10 = 1，进位为 1
carryBit = sum / 10;
// 获取当前计算结果的个位数
// 比如 7 + 8 = 15
// 那么 sum % 10 = 5
int diget = sum % 10;
// 构建一个节点用来存放这个个位数
ListNode digetNode = new ListNode(diget);
// 把这个节点插入到结果链表中
// 注意是插入，越后面计算的结果越在链表的前面
// 一开始，dummy 后面没有其它节点，当发生求和计算时
if(dummy.next == null){
// 第一个计算结果直接加入到 dummy 后面
dummy.next = digetNode;
}else{
// 新的节点的 next 指针为之前的虚拟头节点 dummy 后面的那个节点
digetNode.next = dummy.next;
// 更新 dummy 的 next 指针指向的节点
dummy.next = digetNode;
}
}
// 最后返回结果链表的头节点就行，即虚拟头结点的下一个节点
return dummy.next;
}
}
