LeetCode 2 两数相加
题目描述
链接:https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2ckc81c?envType=featured-list&envId=2ckc81c
难度:中等
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
提示:
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
- 数字按照逆序排序的意思就是,头节点是个位数,下一节点是十位数,依次类推。如果相加大于等于10,则需要进位,把位数加到后面的和中
- 两个链表的长度不一定一样
解法
遍历两个链表,然后依次取节点元素相加。如果相加大于等于10,则需要进位,把位数加到后面的和中。
两个链表的长度不一定一样。遍历时,如果短的遍历完了,相加按照0即可。
注意如果链各个链表都加完了,进位还为1,链表还有下一个节点,值为1。
还需要注意的是,在第一次循环时,我们无法往一个空节点的末尾添加节点。这里的技巧是,创建一个哨兵节点(dummy node),当成初始的「空链表」。循环结束后,哨兵节点的下一个节点就是最终要返回的链表头节点。
代码如下:
from typing import Optionalclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:# cur_node是当前链表,dummy_node是哨兵节点cur_node = dummy_node = ListNode()# carry用来记录上次两数相加进位的数字carry = 0# 如果两个链表有一个不为空,或者进位的不为0,执行下面的逻辑while l1 or l2 or carry != 0:# 当前的和为链表两个节点数字相加,再加上上一次进位的数字,注意链表长度可能不一样,如果短的那个没有节点了,就取0即可carry = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry# 下一个节点的值,取和对10的余数即可cur_node.next = ListNode(carry % 10)# 更新当前节点为下一个节点cur_node = cur_node.next# 新的进位是除以10的商carry //= 10# 最后遍历参数链表里下一个节点l1 = l1.next if l1 else Nonel2 = l2.next if l2 else None# 哨兵节点的下一个节点即为结果节点return dummy_node.next# 辅助函数:用来创建链表
def build_link(l : Optional[list]):head = current_node = Nonefor ele in l:if current_node:current_node.next = ListNode(ele)current_node = current_node.nextelse:head = current_node = ListNode(ele)return head# 辅助函数:用来打印链表
def print_node(n : Optional[ListNode]):l = []while n:l.append(n.val)n = n.nextprint(l)if __name__ == "__main__":l1 = [9, 9, 9, 9, 9, 9, 9]l2 = [9, 9, 9, 9]link1 = build_link(l1)link2 = build_link(l2)res = Solution().addTwoNumbers(link1, link2)print_node(res)
复杂度
时间复杂度:O(n)
空间复杂度:O(1)
相关文章:
LeetCode 2 两数相加
题目描述 链接:https://leetcode.cn/problems/add-two-numbers/?envTypefeatured-list&envId2ckc81c?envTypefeatured-list&envId2ckc81c 难度:中等 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式…...
springboot项目启动失败,不打印报错详细信息(启动打印日记问题)
1:出现这种我问题一般都是日记的问题,查看控制台启动打印的第一句,为什么启动失败,需要用那个日记 2:如果使用的是log4j或者logback与slf4j都是默认在依赖web自带的如下 <dependency><groupId>org.springf…...
MyBatis (where、set、foreach)标签
where标签 在上一节SQL 语句中加入了一个条件“11”,如果没有加入这个条件,那么可能就会变成下面这样一条错误的语句。 SELECT id,name,url,age,country FROM website AND name LIKE CONCAT(%,#{name},%)显然以上语句会出现 SQL 语法异常,但…...
flutter开发之安装dart
1、在MacOS系统中打开终端,进入到官网Get the Dart SDK | Dart brew tap dart-lang/dartbrew install dart 注意:若显示没有brew,请先执行第二步骤,如下: 2、打开homebrew的官网Homebrew — The Missing Package Man…...
向量召回:深入评估离线体系,探索优质召回方法
向量召回:深入评估离线体系,探索优质召回方法 1.简介 近年来,基于向量进行召回的做法在搜索和推荐领域都得到了比较广泛的应用,并且在学术界发表的论文中,基于向量的 dense retrieve 的方法也在不少数据集上都战胜了 sparse retrieve,吸引了越来越多的关注。在内网的不…...
播放器缓存队列bug解决方案
背景 我在开发一个播放器的缓存队列时,遇到一个bug,导致包和帧无法被下一个模块读取 找了半天,原来是队列中的包和帧数据要进行内容的刷新暂存 包数据和帧数据不能直接放入队列 //入队,包进队列 int AVPacketQueue::Push(AVPacket *val,i…...
React拖拽实践
当涉及到前端开发中的用户体验时,拖拽功能是一个常见而重要的需求。在React中,实现拖拽功能可以通过多种方式完成,但通常需要深刻理解React的状态管理、事件处理和DOM操作。本文将探讨React中拖拽的实践,包括基本原理、拖拽库的使…...
Stable Diffusion绘图,lora选择
best quality, ultra high res, (photorealistic:1.4), 1girl, off-shoulder white shirt, black tight skirt, black choker, (faded ash gray hair:1), looking at viewer, closeup <lora:koreandolllikeness_v20:0.66> 最佳品质,超高分辨率,&am…...
kube-controller-manager和kube-scheduler不能正常启动
kube-controller-manager-k8s-worker01和kube-scheduler-k8s-worker01没有启动起来 原因: 解决:进入/etc/kubernetes/manifests 编辑 将镜像地址修改为 然后重启kubelet:systemctl restart kubelet.service...
Mac OS m1 下安装Gradle5.1
1. 下载、解压 1.1 下载地址 https://gradle.org 往下翻 选择 5.1 或者选择 任何 你想要的版本 ,点击 binary-only 即可下载 . 1.2 解压到指定目录 2. 配置环境变量 2.1 编辑环境文件 vi ~/.bash_profile #GRADLE相关配置 GRADLE_HOME/Users/zxj/Documents/devSoft/grad…...
JUC并发编程面试题(自用)
线程池 1 线程池的作用:提高线程的利用率,线程复用,频繁的创建和销毁线程非常浪费资源 线程池的七大参数: corePoolSize(核心线程数):线程池中始终保持的活动线程数,即使它们处于空…...
Redis分布式会话
当探讨Redis分布式会话管理时,以下是更加详细的知识点: 1. 会话管理的挑战: 在分布式应用程序中,每个用户请求可能由不同的服务器处理。这导致了会话数据的分散性,需要一种方法来维护一致性的用户会话状态。 2. Redi…...
程序员大厂之鹅厂探秘
...
【Java 进阶篇】深入理解 JavaScript DOM Node 对象
在前端开发中,与HTML文档进行交互是一项基本任务。文档对象模型(Document Object Model,简称DOM)为开发者提供了一种以编程方式访问和操作HTML文档的方式。DOM的核心是节点(Node)对象,它代表了文…...
测试用例基础
测试用例的基本要素 测试环境, 操作步骤, 测试数据, 预期结果 测试用例的设计方法 基于需求的设计方法 需求文档 -> 梳理需求(掌握需求) -> 针对文档设计测试用例 只是针对需求进行大概的测试 具体的设计方法 等价类 等价类: 依据需求将输入(特殊情况…...
“Flex弹性布局、轮播图mock遍历数据和首页布局解析与实践“
目录 引言1. Flex弹性布局介绍及使用什么是Flex弹性布局?Flex容器与Flex项目Flex属性详解 2. 轮播图mock遍历数据简述轮播图的作用和意义处理mock数据的重要性使用Mock模拟数据遍历 3. 首页布局总结 引言 在现代网页开发中,灵活性和响应式布局是至关重要…...
自动化办公篇之python
1、如果没有安装xlwings库,先在控制台pip install xlwings,然后点击运行,创建四个空excel表 。 import xlwings as xw app xw.App(visibleTrue,add_bookFalse) for dept in ["技术部","销售部","运营部","财务部&q…...
华为云云耀云服务器L实例评测|使用sysbench对云耀云服务器mysql的性能测试
目录 引言 1 在centos上安装mysql 1.1 在云服务器上安装 Docker 1.2 在 Docker 中运行 MySQL 容器 2 安装sysbench并进行性能测试 2.1 安装和配置 sysbench 2.2 运行 sysbench 性能测试 3 分析测试结果 3.1 运行结果 3.2 对运行结果进行翻译 3.3 性能分析 4 清理…...
【译】快速开始 Compose 跨平台项目
原文: Compose Multiplatform application 作者:JetBrains 注意 Compose Multiplatform 中的 iOS 部分目前处于 Alpha 状态。以后可能会有不兼容的更改,届时也许需要手动进行迁移。 你可以使用这个模板来开发同时支持桌面、安卓和 iOS 的跨平…...
高性能服务器之mysql数据库连接池设计与实现
高性能服务器之mysql数据库连接池设计与实现 链接:https://pan.baidu.com/s/1ISZ1Sy087GUeaekW3sV_oA?pwd0t9q 内存泄漏 链接:https://pan.baidu.com/s/1AWPnbuzVSpoP-CnEgJk5hg?pwdaieq 提取码:aieq 线程池 链接:https://pan…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
