img
提示:
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
本题其实就是用一个链表存储一个数字(逆序存储),你需要给它计算出结果后在 逆序 存储到一个链表中返回。
所谓加法的运算规则:从两个数的最低位进行计算,进行到下一位的时候需要考虑进位问题。一直到最后,而本题所给的链表刚好可以用来直接计算,因为链表头都是数字最低位可以直接相加,然后一直遍历到结束。可以用一个常数表示进位。
在具体实现(链表)的时候:
创建新的链表,每次将计算的数值插入到链表尾部即可。
需要准确表示进位,并且最后要考虑以下进位
妥善返回正确节点,可以用一个头节点用来使得所有节点都正常操作,而不需要特殊判断。通过代码第一次比较啰嗦的写法:
当然,如果你遍历链表把各个数字取出来,使用字符串、数字转换然后相加得到一个数字,最后在转成字符串、链表的理论可以,可以自行实现。
优化后的代码为:
//更简洁的写法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node=new ListNode(0);
ListNode team=node;
int jin=0;//进位
while(l1!=||l2!=)
{
int num=jin;
if(l1!=)
{
num =l1.val;l1=l1.next;
}
if(l2!=)
{
num =l2.val;l2=l2.next;
}
jin=num/10;
num%=10;
team.next=new ListNode(num);
team=team.next;
}
if(jin!=0)team.next=new ListNode(jin);
return node.next;
}
两数相加2(力扣445)
题目描述:
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:
输入:(7 -> 2 -> 4 -> 3) (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
本题的话和上面不一样链表不是逆置的,但是加法运算其实需要从最后面对齐开始,也就是理论上应该从链表尾部开始向前,但是这是个单链表,这样运算的话时间复杂度太高,所以我们要用空间换时间:用栈来解决。
将链表的节点依次放到两个栈中,然后两个栈同时取数计算。但是待返回的是个链表,所以采取头插法即可(如果不头插最后反转也可),具体流程可以参考如下图:
逻辑
实现代码为:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer>stack1=new Stack<>;
Stack<Integer>stack2=new Stack<>;
while (l1!=)
{
stack1.add(l1.val);
l1=l1.next;
}
while (l2!=)
{
stack2.add(l2.val);
l2=l2.next;
}
ListNode val=new ListNode(0);//带头结点
int moreadd=0;//余数
while (!stack1.isEmpty||!stack2.isEmpty||moreadd!=0)
{
int num=moreadd;//num=余数 链表1 链表2
if(!stack1.isEmpty)
num =stack1.pop;
if(!stack2.isEmpty)
num =stack2.pop;
moreadd=num/10;
num=num;
//链表头插
ListNode node=new ListNode(num);
node.next=val.next;
val.next=node;
}
return val.next;
}
}
结语
到这里,大数的加减乘除基本都讲解完啦,不知道你有没有收获,因为这里的大数都是用字符串的方式存储和处理,遇到的最多,但是也可能遇到一些链表、数组等其他形式存储的需要处理,但是整体的思想都是一样的。
光看没有还要多多练习对应的题目,当然本人水平有限上面理解可能有误或者不到位还请指正!