首页 > 编程语言 >两数相加 链表C++

两数相加 链表C++

时间:2024-08-25 22:57:58浏览次数:13  
标签:ListNode 相加 C++ 链表 tail l2 l1 carry

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

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

你可以假设除了数字 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]

由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为 n1,n2,进位值为 carry,则它们的和为 n1+n2+carry;其中,答案链表处相应位置的数字为 (n1+n2+carry)mod10,而新的进位值为 (n1+n2+carry)/10。

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

此外,如果链表遍历结束后,有 carry>0,还需要在答案链表的后面附加一个节点,节点的值为 carry。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
         ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;


    }
};

标签:ListNode,相加,C++,链表,tail,l2,l1,carry
From: https://blog.csdn.net/2403_85903590/article/details/141536751

相关文章

  • (算法)最⻓公共前缀————<链表—模拟>
    1.题⽬链接:14.最⻓公共前缀2.题⽬描述:3.解法:算法思路:解法⼀(两两⽐较):我们可以先找出前两个的最⻓公共前缀,然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较,这样就可以找出所有字符串的最⻓公共前缀。C++算法代码: classSolution{public: stringlongestCommonPr......
  • (算法)K个⼀组翻转链表————<链表—模拟>
    1.题⽬链接:25.K个⼀组翻转链表2.题⽬描述:3.解法(模拟):算法思路:本题的⽬标⾮常清晰易懂,不涉及复杂的算法,只是实现过程中需要考虑的细节⽐较多。我们可以把链表按K个为⼀组进⾏分组,组内进⾏反转,并且记录反转后的头尾结点,使其可以和前、后连接起来。思路⽐较简单,但是实......
  • c++随机生成图画
    话不多说直接上代码:#include<bits/stdc++.h>#include<windows.h>#include<stdlib.h>#include<cstdio>#include<iostream>#include<string>#include<stdio.h>#include<ctime>#include<conio.h>#include<time.h>......
  • 【C++ Primer Plus习题】5.10
    问题:解答:#include<iostream>usingnamespacestd;intmain(){ intcount=0; cout<<"请输入星星的行数:"; cin>>count; for(inti=0;i<count;i++) { for(intj=0;j<count-i-1;j++) { cout<<&qu......
  • 【C++ Primer Plus习题】5.9
    问题:解答:#include<iostream>#include<cstring>usingnamespacestd;#defineSIZE20intmain(){ stringwords[SIZE]; stringdone="done"; intcount=0; while(true) { cout<<"请输入单词:"<<endl; c......
  • windows vscode平台配置C++环境
    背景: windows系统,下载vscode1.安装编译器https://github.com/msys2/msys2-installer/releases/2. 安装所需编译工具 自动打开mysys2终端后:#官方提供指令pacman-Smingw-w64-ucrt-x86_64-gcc#推荐指令pacman-S--neededbase-develmingw-w64-ucrt-x86_64-t......
  • 蓝桥杯青少组C++中级部分tj
    1比较难的一次考试,虽然难度低于预期,但依然打得不好。选择这部分比较难,尤其是\(\text{T4}\)考得阅读程序,结果没在选项里,其他有逻辑运算,进制运算,其余的比较简单。个人答案:\(\text{CBDAB}\)编程只记得\(1\),\(2\),\(4\),\(3\)过了,\(5\)\(6\)没写出来,\(1\)很简单的模拟,......
  • C++编程-数据排序2
    关于以后的更新已经8月25号了,即将接近CSP-J/S,因此,在数据排序算法更新完后,我们会重点更新CSP的试卷以及知识点,希望大家在考试中旗开得胜!回顾数据排序1在数据排序1中,我们讲解了选择、冒泡、插入、桶、快速排序,并留下了2道题目,今天就来解答这两道题目一:冒泡排序#include<st......
  • C/C++、Java、Python全面比较
    以下是对C/C++、Java、Python三种编程语言的全面比较,以表格形式呈现:特性/语言C/C++JavaPython类型系统静态类型静态类型动态类型内存管理手动管理自动管理(垃圾回收)自动管理(垃圾回收)编译/解释编译型编译型(通过JVM解释执行)解释型性能高(直接编译成机器码)中等(通过JIT优化)较低(解......
  • 从零开始学习C++之枚举与模拟
    枚举和模拟是C++中最为基础的算法,也是之后赛时部分分的算法首选。枚举顾名思义,枚举就是将所有值全部扫一遍。枚举算法的流程图如下:我们很容易就可以写出伪代码:for(枚举区间){ 代码,例: if(条件) { 输出 }}模拟模拟就是将做的事情通过程序一步步完成,有时候很简......