首页 > 其他分享 >2. 两数相加题解

2. 两数相加题解

时间:2024-09-28 18:01:42浏览次数:6  
标签:tmp ListNode 题解 相加 tail l2 l1 sum

题目描述

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

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

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

示例 1:

img

输入: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]

提示:

  • 每个链表中的节点数在范围 [1, 100]
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

题解

思路

本题与Acwing中的大数相加思路类似,模拟实际加法计算流程。

需要注意的有:

  1. 计算结果是否有前导零,即0010,要修改为10。不过,此题已经注明不会有前导零
  2. 进位,尤其是最后进位
  3. 扫尾,即处理两个输入长度不一致的情况

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // 結果要以逆序的方式输出,故要用尾插法
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        int carry = 0; // 进位
        int sum;
        int l1_tmp, l2_tmp;
        while (l1 || l2 || carry) { // 包含扫尾、最终进位
            l1_tmp = l1 ? l1->val : 0;
            l2_tmp = l2 ? l2->val : 0;
            sum = l1_tmp + l2_tmp + carry;
            carry = sum / 10;
            if (head == nullptr) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        return head;
    }
};

如果不依照大数相加的代码模板,要写的代码会比较多,因此记忆模板是一个很好的学习方法。

标签:tmp,ListNode,题解,相加,tail,l2,l1,sum
From: https://www.cnblogs.com/coder-shane/p/18438229

相关文章

  • 【自创题】云梯 题面+题解
    题目描述这是晴练P2876云梯的题面。原链接unicornFairy开始了新的学期。学校换了一个新校长,随之而来的是周五放学的时间由晚上七点半延时到了晚上八点半。unicornFairy认为这很不公平,所以她准备抢先一步回家。晚饭后,unicornFairy来到了一处没有监控的围墙旁。小马将援助unicorn......
  • BLE Audio显示连接成功,但没有音乐播放问题解决方案
    背景最近一直在搞这个问题,和原厂一起分析,背景可以参考前面的文章https://blog.csdn.net/Jzj1234555/article/details/142518444?spm=1001.2014.3001.5501https://blog.csdn.net/Jzj1234555/article/details/142595444?spm=1001.2014.3001.5501解决方案今天原厂承认了他......
  • P5165 xtq的棋盘 题解
    这个题也可以用矩阵加速解决。先考虑70pts的做法,我们设\(f_i\)为从\(i\)位置到达\(0\)的期望步数,并尝试用\(f_n\)表示出所有\(f_i\)并利用\(f_0\)解出\(f_n\)然后回带即可。具体地,设\(f_i=a\timesf_n+b\),\(f_{i-1}=c\timesf_n+d\),则由于:\[f_i=pr......
  • Codeforces Round 975 (Div. 2) 题解:D、E
    第一次进前50,上分最爽的一次D.Speedbreaker对\(a\)按照时间升序排序,不难发现,对于升序排序后的数组,当我们搜到时间\(t\)时,记录已经搜过的时间对应原城市编号最小值为\(l\),最大值为\(r\),则我们一定要在\(a_t\)时间之前走过所有\([l,r]\)之间的城市。则若\(r-l+1>a_t\)则无解,因......
  • [USACO22DEC] Breakdown P 题解
    T1[USACO22DEC]BreakdownP比较显然的一点是,一次加一条边/一次删一条边,显然转化,这是显然的一条套路。这题的\(K\le8\),很有意思的数据范围,然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑\(K\le4\)的情况,令\(\mathit{st}\)表示折半搜索中考虑的起点。维......
  • [NOIP2017 提高组] 奶酪 题解
    题目背景NOIP2017提高组D2T1题目描述现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为 z=0,奶酪的上表面为 z=h。现在,奶酪的下表面有一只小老鼠Jerry,......
  • 洛谷P1827 [USACO3.4] 美国血统 题解
    上题目:题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树,并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和......
  • 洛谷P1162 填涂颜色题解
    老规矩上题目:题目描述由数字 00 组成的方阵中,有一任意形状的由数字 11 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 22。例如:6×66×6 的方阵(n=6n=6),涂色前和涂色后的方阵如下:如果从某个 00 出发,只向上下左右 44 个方向移动且仅经过其他 00 的情况下,无法......
  • 题解 HZOJ 284 超市卖货 C/C++
    题目传送门:超市卖货-题目-OnlineJudge(haizeix.com)https://oj.haizeix.com/problem/284思路:每次寻找价格最高的商品,并尝试卖掉它:寻找未卖出商品的日期,优先锁定其保质期最后一天,若该日期已卖出则继续向前寻找能找到未卖出商品的日期时,收入增加,标记该日期代码实现:为......
  • Echarts图表知识点汇总及请求django服务器后端跨域问题解决
    1.引入echartsvue3中通过npm引入:npminstallecharts--saveimport*asechartsfrom'echarts';//基于准备好的dom,初始化echarts实例varmyChart=echarts.init(document.getElementById('main'));//绘制图表myChart.setOption({title:{text:'ECha......