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…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...