两个数相加

简介: 两个数相加

题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807. 示例 2:

输入:l1 = [0], l2 = [0] 输出:[0] 示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]

思路介绍

首先链表与数组不同,我们无法在常量时间内访问单链表中的随机元素。如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。题目说明是逆序的方式,链表第一个数字即为个位,循环遍历至链表最后一位,选择使用while循环的方式进行遍历,只要l1,l2不为空或者carry不为零,一直重复操作。

其次需要考虑到数字相加进位的情况,

1.小于10,不需要进位 2.大于等于10,最多只需要进一位计算求进位和余数。

如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 00

存在一个链表next不是空,然后将指针指向下一个值,对下一个节点处理。

当链表节点都为空之后,别忘了对进位进行判断,如果最后还有进位的话,增加一个节点

代码

        //root存放结果,cursor为root的尾指针
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int jinwei = 0; //进位
        while (l1!=null||l2!=null|| jinwei!=0){
        
            //int s1 = l1.val;
            //int s2 = l2.val;
            //如果其中有一个到达结尾了,那么这个链表这一位的的数字就为0。
            int s1 = l1!=null?l1.val:0;
            int s2 = l2!=null?l2.val:0;
               //两个链表的两位相加
            int sum = s1+s2+jinwei;
            jinwei = sum /10;
            int yushu = sum%10;
            ListNode sumNode = new ListNode(yushu);
            //创建一个节点接入root后面
            cursor.next = sumNode;
            cursor = sumNode;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
​
  
        return root.next;

总结

此题不算难,主要需要考虑:

1.链表长度不相等的情况下需要补齐链表取零,

2.两个数相加进位的问题

3.链表遍历结束后有进位的情况,比较容易遗忘

相关文章
|
6月前
|
算法
给定两个数,求这两个数的最大公约数
给定两个数,求这两个数的最大公约数
|
3天前
|
C语言
计算一个数的 n 次方
【10月更文挑战第23天】计算一个数的 n 次方。
9 3
|
2月前
|
机器学习/深度学习 网络协议 Windows
几个数相加
几个数相加。
41 4
打印0~100000之间的水仙花数, 水仙花数指一个n位数,其各位数的n次方之和正好等于该数本身
打印0~100000之间的水仙花数, 水仙花数指一个n位数,其各位数的n次方之和正好等于该数本身
104 0
统计正数和负数的个数然后计算这些数的平均值(循环、数组解法)
统计正数和负数的个数然后计算这些数的平均值(循环、数组解法)
195 0
非负数组中两个数相与的最大结果
非负数组中两个数相与的最大结果
|
存储
如何快速算出一个数的n次方?
先计算存储下来再求值,不失为一种好方法;但亦可以在计算 的同时判断 分解为 的幂(即转为 进制)后是否含 ,边计算边乘。 形式化地,对于 位,其代表的幂 为 ()。 这样,我们由低位向高位计算,每次将底数平方即可。 下面两份伪代码,分别对应这种方法的如上两种实现。
909 0
如何快速算出一个数的n次方?
(JAVA编程练习):一个整数,它加上100后是平方数,再加上168又是一个平方数,该数是?+ 输入三个数,进行小到大排序。
(JAVA编程练习):一个整数,它加上100后是平方数,再加上168又是一个平方数,该数是?+ 输入三个数,进行小到大排序。
(JAVA编程练习):一个整数,它加上100后是平方数,再加上168又是一个平方数,该数是?+ 输入三个数,进行小到大排序。
两个数相加
两个数相加
108 0
两个数相加