一、题目
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
二、示例
2.1> 示例1：
【输入】l1 = [7,2,4,3], l2 = [5,6,4]
【输出】[7,8,0,7]
2.2> 示例2：
【输入】l1 = [2,4,3], l2 = [5,6,4]
【输出】[8,0,7]
2.3> 示例3：
【输入】l1 = [0], l2 = [0]
【输出】[0]
提示：
- 链表的长度范围为
[1, 100] 0<= node.val <=9- 输入数据保证链表代表的数字无前导 0
- 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
三、解题思路
根据题意，我们要对两个链表进行相加操作，但是，两个链表的长度却不一定是相同的，那么我们就需要考虑这种相加的操作要从链表尾部开始，并且随着两个节点相加如果大于等于10的话，是要有进位操作的。所以，我们先分别遍历两个链表l1和l2，将其放入到堆栈结构中，这样，栈顶的元素就是链表中的末尾元素了。随着对堆栈执行出栈操作，来计算节点之和。上面我们提到的进位操作，这个我们用int carry来表示。具体操作，如下图所示：
四、代码实现
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<ListNode> dequeL1 = new ArrayDeque(), dequeL2 = new ArrayDeque();
while(l1 != null) {
dequeL1.addLast(l1);
l1 = l1.next;
}
while(l2 != null) {
dequeL2.addLast(l2);
l2 = l2.next;
}
ListNode temp = null;
int carry = 0;
while(!dequeL1.isEmpty() || !dequeL2.isEmpty() || carry != 0) {
int val1 = dequeL1.isEmpty() ? 0 : dequeL1.removeLast().val;
int val2 = dequeL2.isEmpty() ? 0 : dequeL2.removeLast().val;
ListNode node = new ListNode((val1 + val2 + carry) % 10);
if (temp != null) node.next = temp;
temp = node;
carry = (val1 + val2 + carry) / 10;
}
return temp;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」