LeetCode.面试题02.05-链表求和-题解分析

题目来源

面试题 02.05. 链表求和

题目详情

给定两个用链表表示的整数,每个节点包含一个数位。

这些数位是反向存放的,也就是个位排在链表首部。

编写函数对这两个整数求和,并用链表形式返回结果。

示例:

输入: (7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出: 2 -> 1 -> 9,即912

进阶: 思考一下,假设这些数位是正向存放的,又该如何解决呢?

示例:

输入: (6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出: 9 -> 1 -> 2,即912

题解分析

题目的要求是对链表的节点进行求和。题目的难点在于两个链表的长度可能不同,而且每个节点只能存放一个数位的元素。

这里最直接的解法就是模拟法,或者叫做遍历法,同时遍历这两个链表并进行加法运算,构造出一个新的结果链表。考虑到这里是一个反向链表,可以直接从头开始遍历,因此,这个题目也可以看成是一个子问题的题目即使用递归的思想解决。

使用递归的方法相对容易理解,而且写法比较简单。在每一轮递归的过程中,需要同时记录进位,在两个链表都遍历结束的时候,因为每个节点只能存放一个位的元素,因此可能会存在进位元素,需要放在一个新的尾部节点中。

java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return dfs(l1, l2, 0);
    }

    private ListNode dfs(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        int sum = carry;
        if (l1 == null && l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        } else if (l2 == null && l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        } else if ((l1 != null) && (l2 != null)) {
            sum += (l1.val + l2.val);
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode node = new ListNode(sum % 10);
        node.next = dfs(l1, l2, sum / 10);
        return node;
    }
}
Either Excellent or Rusty
本文转载于网络 如有侵权请联系删除

相关文章

  • 为什么打工人996会猝死,而老板007不会?

    今天周末,给大家分享一个漫画,来源:程序员吴小胖为什么打工人996会猝死,而老板007却不会?一起来看看“真相”吧!对此,你有什么看法?欢迎评论区留言讨论哦~

  • dubbo 配置 loadbalance 不生效?撸一把源码

    背景很久之前我给业务方写了一个dubboloadbalance的扩展(为了叙述方便,这个loadbalance扩展就叫它XLB吧),这两天业务方反馈说XLB不生效了我心想,不可能啊,都用了大半年了~排查于是我登上不生效的consumer机器进行排查,还好我留了一手,当XLB加载时,会打印一行日志看了下这个服务,并没有打印日志,说明XLB并没有加载成功于是,我就去问对应的开发,有按照我的文档配置loadbalance吗?答复:完全按照文档配置这下我就有点不相信了,但转念一想,配置loadbalance如此简单,不应该出错啊,我的文档和他的应用都在xml文件中配置了consumer的loadbalance<dubbo:consumerloadbalance="xlb"/>复制抱着试一试的态度,拉取了他们项目的代码,发现配置确实如上,但我发现他们的application.properties配置文件也配了一个consumer的属性dubbo.consumer.check=false复制以多年和dubbo打交道的经验来说,这里有问题,又确认了代码,确实xml和a

  • kube-proxy中使用ipvs与iptables的比较

    Iptables模式kube-proxy就可以通过Service的Informer感知到APIServer中service和endpoint的变化情况。而作为对这个事件的响应,它就会在宿主机上创建这样一条iptables规则(你可以通过iptables-save看到它)。这些规则捕获到service的clusterIP和port的流量,并将这些流量随机重定向到service后端Pod。对于每个endpoint对象,它生成选择后端Pod的iptables规则。如果选择的第一个Pod没有响应,kube-proxy将检测到到第一个Pod的连接失败,并将自动重试另一个后端Pod。拓扑图:iptables是一个Linux内核功能,是一个高效的防火墙,并提供了大量的数据包处理和过滤方面的能力。它可以在核心数据包处理管线上用Hook挂接一系列的规则。iptables模式中kube-proxy在NATpre-routingHook中实现它的NAT和负载均衡功能。这种方法简单有效,依赖于成熟的内核功能,并且能够和其它跟iptables协作的应用融洽相处。因为它纯粹是为防火墙而设计且基于内核规则列表,ku

  • 小米路由器常见故障处理方法

    问题1.忘记路由器用户名和密码。路由器可以通过Reset键恢复出厂设置。操作方法为:在路由器通电的情况下,使用尖状物长按路由器的Reset按键,直至系统指示灯快速闪烁时松开,路由器将自动恢复出厂设置并重启。恢复出厂设置后,默认管理地址是tplogin.cn,首次登录时需自定义用户名和密码。问题2.无法登录路由器WEB管理界面。请通过以下方法进行检查:1.观察指示灯的状态,检查相应端口线缆是否正常连接;同时确认端口没有被禁用,可以换另外一个物理端口登录路由器;2.如果是通过本地计算机管理路由器,请确保本地计算机为“自动获得IP地址”;3.如果您之前管理过路由器,请确认是否更改过路由器管理IP或管理端口,如果忘记了路由器的管理IP或管理端口,建议您通过Reset键将路由器恢复出厂设置后再进行管理。问题3.不能正常浏览管理界面。1.显示异常,请升级或更换其他浏览器;2.窗口弹出被禁止,请降低浏览器安全设置。 4、我的设备支持5GWiFi,为什么搜索不到5GWiFi信号?5G信道有很多,目前国内只允许开启部分信道,其他的都不可用。部分用户购买的俗称非“国行”的手机可能工作在国内不支持的信道。遇

  • [第37期] 了解下git文件名大小写

    背景下午在搞代码部署的时候,遇到一个文件名大小写的问题,问题比较简单,但是也简单整理下,分享给大家。正文下午在搞代码部署的时候,线上编译失败了,看了下错误日志:#70.984$BABEL\_ENV=productionwebpack--configwebpack/webpack.config.prod.js--colors #719.58ModuleNotFoundError:Modulenotfound:Error:Can'tresolve'./UserModal'in'/workspace/src/pages/User/UserList'复制文件没找到,可是我看了看代码,UserModal这不是好好地在这吗?到线上仓库看了一下,文件名是小写的userModal。怪不得文件找不到。知道错误原因就很好办了。直接把git的忽略大小写关了:gitconfigcore.ignorecasefalse复制然后重新提交,就OK了。除去这个做法,你也可以这样:gitmvFilefile.tmp gitmvfile.tmpfile复制然后重新提交,问

  • Flink SQL DDL 和 窗口函数实战

    一、FlinkSQLDDL2019年8月22日,Flink发布了1.9版本,社区版本的Flink新增了一个SQLDDL的新特性,但是暂时还不支持流式的一些概念的定义,比如说水位。二、定义createtable语句从kafka中读取数据可以体验一下,如果使用ddl的方式直接定义一个表从kafka中读取数据,并定义成一个表CREATETABLEuser_visit( user_nameVARCHAR, tstimestamp )WITH( 'connector.type'='kafka', 'connector.version'='0.10', 'connector.topic'='flink-test-05', 'connector.startup-mode'='latest-offset', 'connector.properties.0.key'='zookeeper.connect',

  • lnmp修改文件上传限制

    记录一下在lnmp环境下,修改php上传文件限制需要修改的配置项。phpphp方面主要修改三个配置项:upload_max_filesize#示例配置upload_max_filesize=20M; post_max_size#示例配置post_max_size=40M max_execution_timemax_execution_time=300 一般推荐post_max_size略大于upload_max_filesize,max_execution_time根据设置的最大文件大小来修改,0为不限制,但不推荐设置0。 另外,如果开启了内存限制(memory_limit),文件上传大小要小于内存限制。nginx如果只是修改了php的配置,会发现还是无法上传,因为nginx方面也做了限制,所以也需要修改nginx的配置。 nginx方面主要有这三个配置:keepalive_timeoutkeepalive_timeout300;client_header_timeoutclient_header_timeout300s;client_body_timeoutclient_body_t

  • 交叉验证,K折交叉验证的偏差和方差分析

    交叉验证交叉验证是一种通过估计模型的泛化误差,从而进行模型选择的方法。没有任何假定前提,具有应用的普遍性,操作简便,是一种行之有效的模型选择方法。1.交叉验证的产生人们发现用同一数据集,既进行训练,又进行模型误差估计,对误差估计的很不准确,这就是所说的模型误差估计的乐观性。为了克服这个问题,提出了交叉验证。基本思想是将数据分为两部分,一部分数据用来模型的训练,称为训练集;另外一部分用于测试模型的误差,称为验证集。由于两部分数据不同,估计得到的泛化误差更接近真实的模型表现。数据量足够的情况下,可以很好的估计真实的泛化误差。但是实际中,往往只有有限的数据可用,需要对数据进行重用,从而对数据进行多次切分,得到好的估计。2.交叉验证方法留一交叉验证(leave-one-out):每次从个数为N的样本集中,取出一个样本作为验证集,剩下的N-1个作为训练集,重复进行N次。最后平均N个结果作为泛化误差估计。留P交叉验证(leave-P-out):与留一类似,但是每次留P个样本。每次从个数为N的样本集中,取出P个样本作为验证集,剩下的N-P个作为训练集,重复进行CPN次。最后平均N个结果作为泛化误差估

  • 码农深夜骑车逆行被拦后爆发大哭,称压力好大!

    阅读本文大概需要2.3分钟。今天本来是准备发面经文章的,无意看到“小伙骑车逆行被拦后爆发”的视频,心里面堵堵的,挺心酸。事件大概经过如下:杭州一小伙骑单车逆行,被交警拦下后,小伙接了一个电话。没想到打完电话,小伙子当即摔了手机,彻底崩溃了。他情绪非常激动,大声喊着自己每天要加班到十一二点,自己的女朋友忘了带钥匙了,让他送钥匙,公司也在催他,两边都在催他,他真的觉得好累。暖心的交警们,一直陪在小伙身边,直到他情绪稳定后才离开。前几天的996ICU事件似乎无任何波澜,反正该通宵还是要通宵,该加班的还是要加班,似乎改变不了什么。码农,虽拿着高于其他行业的薪资,却终究还是底层人员!愿大家的孩子不是“码二代”!而是富二代!不管你们有没有感触,反正对我感触很大。完整视频(网上可搜索下,无法上传上来)网友们纷纷表示,太不容易了视频原文大致如下:3月25日,视频中的一幕发生在杭州文一路文菁路口附近,当时傅警官正带队整治电动车的交通违法行为,一位小伙因骑单车逆行被交警拦下。拦下男子的民警傅朝刚说,骑车逆行的小伙子看上去20岁出头,戴着眼镜,斯斯文文,凭他的经验,像是附近IT公司的“码农”。(躺着中枪)被

  • 那些年我们写过的T-SQL(中篇)

    中篇的重点在于,在复杂情况下使用表表达式的查询,尤其是公用表表达式(CTE),也就是非常方便的WITHASXXX的应用,在SQL代码,这种方式至少可以提高一倍的工作效率。此外开窗函数ROW_NUMBER的使用也使得数据库分页变得异常的容易,其他的一些特性使用相对较少,在需要时再查阅即可。本系列包含上中下三篇,内容比较驳杂,望大家耐心阅读:那些年我们写过的T-SQL(上篇):上篇介绍查询的基础,包括基本查询的逻辑顺序、联接和子查询那些年我们写过的T-SQL(中篇):中篇介绍表表达式、集合运算符和开窗函数那些年我们写过的T-SQL(下篇):下篇介绍数据修改、事务&并发和可编程对象表表达式TableExpression是一种命名的查询表达式,代表一个有效的关系表与其他表的使用类似。SQLServer支持4种类型的表表达式:派生表、公用表表达式、视图等。派生表 派生表也称为子查询表,非常的常见,之前介绍相关子查询时那些命名了的外部表均是表表达式。表表达式并没有任何的物理实例化,其优势在于使得代码逻辑清晰并可重用,但对性能并无影响。获取处理订单数超过100的订单年度及其客户数量:SELE

  • java 代码的良好习惯

    有很多书籍提到了代码开发的良好习惯,但是自己看过后,在开发中并不能每次都想起来。在此处开贴做笔记,以后自己开发的代码,必须符合。 不要在一个代码块的开头把局部变量一次性都声明了(这是c语言的做法),而是在第一次需要使用它时才声明。局部变量在声明时最好就进行初始化,或者声明后尽快进行初始化。 包名全部小写,连续的单词只是简单地连接起来,不使用下划线。 类名都以UpperCamelCase风格编写。 方法名都以lowerCamelCase风格编写。 只要是合法的,就把@Override注解给用上。

  • LPC18xx LPC43xx LPC4370 Bootrom USB DFU FPB - Flash Patch and Breakpoint Unit

    WhatisthedifferencebetweenaBootromvsbootloaderonARMsystems Bootrom Bootrom(orBootROM)isasmallpieceofmaskROMorwrite-protectedflashembeddedinsidetheprocessorchip. Itcontainstheveryfirstcodewhichisexecutedbytheprocessoronpower-onorreset. Dependingontheconfigurationofsomestrappinsorinternalfusesitmaydecidefromwheretoloadthenextpartofthecodetobeexecuted andhoworwhethertoverifyitforcorrectnessorvalidity. Sometimesitmaycontainadditionalfunctionality,possiblyusablebyusercodeduringorafterbooting.Someexam

  • 从零开始使用前端开发框架semanticUI(二)用gulp安装semantic UI

    这是一款语义化的UI框架,代码可读性与可理解性很强,界面简洁美观,与bootstrap风格接近,基于jquery,适用响应式布局,提供一些基本模板,兼容Firefox、Chrome、safari,IE10+等浏览器。bootstrap的api自称规范挺好,但是很拗口。SemanticUI在这方面比较有优势。 semanticUI可以有两种方式安装 github仓库直接下载压缩包,使用其中的js和css文件,为元素设定ui类即可。 <head> <linkhref="./semantic.min.css"rel="stylesheet"type="text/css"> <scriptsrc="./jquery.min.js"></script> <scriptsrc="./semantic.min.js"></script> </head> 复制 gulp优点是,你可以自己修改sementicui中的样式,更加灵活。下面是对后者的步骤介绍。 正确安装node、npm、npx node--ver

  • react不使用link进行路由跳转(类组件,函数式组件都有)

    类组件 consthistory=createBrowserHistory({ forceRefresh:true//这个表示url更新会刷新页面,如果不添加不刷新当然你也可以用js刷新哪个效率高还没研究过 }); //之后定义方法触发即可 goSearch(a){ history.push(`/search?drug=${a}`); } 复制 函数式组件 consthistory=useHistory(); history.push(`'/search?a=${value}'`) 复制

  • codeforces 425E

    题意:对于[l1,r1],[l2,r2]...[lm,rm]线段组成的一个集合S,我们定义f(S)为最大的不相交(没有任何公共点)线段数,现在给定n及k,n表示线段范围,即任何[li,ri]有1<=li<=ri<=n,求有多少个集合使得f(S)=k。 思路:刚看到题目感觉不会,也就不多想。。      突然问了下小胖,小胖说他做过,不难。。然后我就慢慢想了。。      仔细想想,确实不难。。      假设现在已经给定了一个S,那么我们怎么求f(S)?      很显然,我们可以贪心,按照r排序,那么我们每次只要取最小r的线段,删除覆盖的,依次做完最后取到的线段肯定最多。。      这么以来对于任意一个集合S,我们肯定可以用最小的有用线段的右端点r来表示其状态。。     &nb

  • Mybatis

    一、什么是Mybatis MyBatis是一款优秀的持久层框架,它支持定制化SQL、存储过程以及高级映射。MyBatis避免了几乎所有的JDBC代码和手动设置参数以及获取结果集。 MyBatis可以使用简单的XML或注解来配置和映射原生信息,将接口和Java的POJOs(PlainOldJavaObjects,普通的Java对象)映射成数据库中的记录。   二、Mybatis相对JDBC有哪些优势 jdbc连接数据库的连接方法: publicstaticvoidmain(String[]args){ Connectionconnection=null; PreparedStatementpreparedStatement=null; ResultSetresultSet=null; try{ //1、加载数据库驱动 Class.forName("com.mysql.jdbc.Driver"); //2、通过驱动管理类获取数据库链接 connection=DriverManager.getConnection("jdbc:mysql://localhost:3306/myb

  • 机器学习--介绍

    1.机器学习:通过对以往历史数据的学习建立一个模型用来预测以后的数据进行预测和分析。     1.1监督学习supervisedlearning      监督学习可以分为生成方法(生成模型generative)和判别方法(判别模型discreiminative)   生成模型:学习联合概率分布p(x,y)      p(y|x)=p(x,y)/p(x)=p(y)p(x|y)/p(y)      比如贝叶斯模型,隐马尔科夫模型(HMM)   判别模型:有数据直接学习f(x)或者条件概率分布p(y|x)       比如:最近邻(KNN),感知机(perception),决策树等              学习过程的三要素:模型(Model)、策略、算法 &nbs

  • javascript设计模式笔记

      观察者模式 观察者模型是非常普遍的一种设计模式,通常会用来在不同系统之间进行解耦     观察者模式:两种关键对象和三种关键操作 subject对象:提供三种基本操作方式:被订阅(注册监听方法register),被取消订阅(移除监听方法remove),触发事件(notify) observers对象:业务逻辑执行对象,监听subject对象的调用 /**@Author:qiao*@Date:2019-06-2911:01:53*@LastModifiedby:qiao*@LastModifiedtime:2019-07-0720:52:58*@Description:练习二完善发布订阅者模型*/ /***观察者模式:两种关键对象和三种关键操作*1)subject对象:提供三种基本操作方式:被订阅(注册监听方法register),被取消订阅(移除监听方法remove),触发事件(notify)*2)observers对象:业务逻辑执行对象,监听subject对象的调用**观察者模型是非常普遍的一种设计模式,通常会用来在不同系统之

  • 53. Maximum Subarray

    Findthecontiguoussubarraywithinanarray(containingatleastonenumber)whichhasthelargestsum. Forexample,giventhearray [-2,1,-3,4,-1,2,1,-5,4],thecontiguoussubarray [4,-1,2,1] hasthelargestsum= 6.     1classSolution{ 2public: 3intmaxSubArray(vector<int>&nums){ 4if(nums.size()==0){ 5return0; 6} 7 8intsum=0; 9intgreatSum=INT_MIN; 10 11for(inti=0;i<nums.size();i++){ 12sum+=nums[i]; 13greatSum=max(greatSum,sum); 14if(sum<0){ 15sum=0; 16} 17} 18returngreatSum

  • 【清北前紧急补课4】国王游戏

    是个垃圾贪心+高精乘除   题目描述 恰逢HHH国国庆,国王邀请nnn位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这nnn位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。 输入输出格式 输入格式: 第一行包含一个整数nnn,表示大臣的人数。 第二行包含两个整数aaa和bbb,之间用一个空格隔开,分别表示国王左手和右手上的整数。 接下来nnn行,每行包含两个整数aaa和bbb,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。 输出格式: 一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。     推一推推一推:可以确定国王的位置是不变的。那么接下来我们就

  • deepin15.11安装过程

    deepin的安装过程。机器为神州Z6,英伟达960m,8G内存。双磁盘双系统,第一块磁盘装win10,deepin安装位置在第二块磁盘。 1、在https://www.deepin.org/download/下载镜像文件和深度启动盘制作工具。 2、打开制作工具制作就行了。 3、安装,这里是win10已经存在的情况下安装deepin,win10是UEFI+GPT安装,也就是说已经存在efi分区,所以没有分efi分区。看官方教程https://www.deepin.org/installation/,安装简体中文就行,文件夹的名称就是英文的,不需要考虑安装英文在换回中文的问题。在安装过程中我选择的是高级模式,第一个简单模式中似乎为只有一个根分区。高级模式需要改变的只有挂载点可空间大小。这里70G的根分区挂载点为/,100G的home分区,挂载点为/home,按官方说明内存8G不需要swap分区。然后选择安装位置为根分区/。然后等待安装。 4、安装完成后弹出、拔下U盘。重启。 5、然后在开机后遇到,在logo界面卡死。于是在启动界面按e进入编辑,然后在倒数第二行的splashquiet后添

相关推荐

推荐阅读