两数相加
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solutuin {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 哨兵节点
ListNode sentinel = new ListNode(0);
// 游标节点
curr = sentinel;
// 进位
int carry = 0
while (l1 != null || l2 != null) {
if (l1 != null) {
carry += l1.val;
l1 = l1.next;
}
if (l2 != null) {
carry += l2.val;
l2 = l2.next;
}
// 当carry大于10的时候需要考虑进位
curr.next = new ListNode(carry % 10);
carry = carry / 10;
curr = curr.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return sentinel.next;
}
}
进阶
如果位数是按正序排列的又该如何求解呢？
445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
import java.util.Stack;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 使用栈反转链表
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
// 哨兵节点
ListNode sentinel = null;
// 进位
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
// 依次弹栈，相加
if (!stack1.isEmpty()) {
carry += stack1.pop();
}
if (!stack2.isEmpty()) {
carry += stack2.pop();
}
// 从个位开始计算, 依次向前，因此新节点应该挂在头部，采用头插法
ListNode node = new ListNode(carry % 10);
node.next = sentinel;
// sentinel始终是新链表的头节点
sentinel = node;
// 进位
carry = carry / 10;
}
return sentinel;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
