文档章节

Leetcode(二):Add Two Numbers

Ambitor
 Ambitor
发布于 2016/04/20 11:37
字数 483
阅读 53
收藏 0
点赞 1
评论 0

Add Two Numbers

题目

Total Accepted: 137297  Total Submissions: 599150  Difficulty: Medium

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Subscribe to see which companies asked this question

解题思路

任意选择一个Node进行迭代,迭代中有几种可能 1、Node1个数少于Node2 2、Node1个数和Node2相等 3、Node1个数大于Node2 分别进行考虑,计算进位和取模,迭代过程中改变Node1及Node2的偏移量,然后从当前偏移量Node2开始Node2的迭代。

代码

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null||l2==null)return null;
            int multiple=0;
            ListNode result=null,nextNode=null;//用来表示结果与下一个Node
            while(l1!=null){
                int n1=0,n2=0,sum=0;
                n1= l1.val;
                if(l2!=null){
                    n2= l2.val;
                    sum=n1+n2;
                    sum+=multiple;
                    multiple=0;
                    if(sum>9){
                       multiple=sum/10;
                       sum=sum%10;
                    }
                    if(result==null){
                        result=new ListNode(sum);
                        nextNode=result;
                    }
                    else{ 
                        nextNode.next=new ListNode(sum);
                        nextNode=nextNode.next;
                    }
                    l2=l2.next;//l2的指针随l1偏移
                    l1=l1.next;
                }else{
                    n1+=multiple;
                    multiple=0;
                    if(n1>9){
                        multiple=n1/10;
                        n1=n1%10;
                    }
                    nextNode.next=new ListNode(n1);
                    nextNode=nextNode.next;
                    l1=l1.next;
                }
            }
            while(l2!=null){//如果l1链表长度少于l2链表长度
                int n2= l2.val;
                n2+=multiple;
                multiple=0;
                if(n2>9){
                    multiple=n2/10;
                    n2=n2%10;
                }
                nextNode.next=new ListNode(n2);
                nextNode=nextNode.next;
                l2=l2.next;
            }
            if(multiple!=0){//迭代完Node1、Node2 最后如果进位不为0 则加一位
                nextNode.next=new ListNode(multiple);
                nextNode=nextNode.next;
            }
            return result;
        }
    }

复杂度

O(n)的时间 O(n)的内存

测试结果

其他思路

后面看到有用递归做这个题目的思路,代码会精简很多,大家可以尝试下

注:版权所有转载请注明出处http://my.oschina.net/ambitor/blog/662824,作者:Ambitor


© 著作权归作者所有

共有 人打赏支持
Ambitor
粉丝 73
博文 30
码字总数 29210
作品 0
高级程序员
Leetcode 1——Two Sum

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may as......

Quincuntial
2017/03/15
0
0
LeetCode:Add Two Numbers - 两个链表逐项做带进位的加法生成新链表

1、题目名称 Add Two Numbers (两个链表逐项做带进位的加法生成新链表) 2、题目地址 https://leetcode.com/problems/add-two-numbers/ 3、题目内容 英文:You are given two linked lists ...

北风其凉
2015/08/27
290
0
LeetCode 001. Two Sum

题目: Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that the......

jzzlee
2015/05/18
0
0
[leetcode] Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers ......

jdflyfly
2014/06/24
0
0
反序存储链表

不接触算法相关的东西快两年多了,真的是生疏了。初步计划是每周抽出些时间在LeetCode上作两道算法题。 明有科举八股,今有LeetCode。 八股定格式而取文采心意,LeetCode定题目且重答案背诵。...

吴七禁
2017/11/11
0
0
Leetcode2——Add Two Numbers

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse or......

Quincuntial
2017/03/16
0
0
LeetCode目录。

按照LeetCode的Tags来区分的话,目前共有34个Tag,只列出已经解决的题,各分类中按照题目编号排序: Linked List。 Solved:21/28 Array。

Leafage_M
2017/11/21
0
0
leetcode-two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example......

梦想游戏人
2016/07/14
10
0
【LeetCode】415 Add Strings (java实现)

原题链接 https://leetcode.com/problems/add-strings/ 原题 Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2. Note: 题目要求 题目......

BookShu
2016/10/26
115
0
LeetCode 002. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers ......

jzzlee
2015/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

看看 LinkedList Java 9

终于迎来了 LinkedList 类,实现的接口就有点多了 Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>。LinkedList是一个实现了List接口和Deque接口的双端链......

woshixin
13分钟前
0
0
算法 - 冒泡排序 C++

大家好,我是ChungZH。今天我给大家讲一下最基础的排序算法:冒泡排序(BubbleSort)。 冒泡排序算法的原理如下: 比较相邻的元素。如果第一个比第二个大(可以相反),就交换他们两个。 对每...

ChungZH
15分钟前
0
0
jquery ajax request payload和fromData请求方式

请求头的不同 fromData var data = { name : 'yiifaa'};// 提交数据$.ajax('app/', { method:'POST', // 将数据编码为表单模式 contentType:'application/x-ww...

lsy999
18分钟前
0
0
阿里P7架构师,带你点亮程序员蜕变之路

前言: Java是现阶段中国互联网公司中,覆盖度最广的研发语言。 掌握了Java技术体系,不管在成熟的大公司,快速发展的公司,还是创业阶段的公司,都能有立足之地。 有不少朋友问,成为Java架...

Java大蜗牛
19分钟前
1
0
Ecstore 在没有后台管理界面(维护)的情况如何更新表的字段

window 系统: 切换到:app\base 目录下: C:\Users\qimh>d: D:\>cd D:\WWW\huaqh\app\base 执行:D:\WWW\huaqh\app\base>cmd update linux 系统: 1># cd /alidata/www.novoeshop.com/app/......

qimh
24分钟前
0
0
设计模式-策略模式

策略模式 解释 对工厂模式的再次封装,使用参数控制上下文信息(将工厂返回的实例赋值给context field) 不会返回bean实例,只是设置对应的条件 调用context的方法(调用field的方法) 用户只...

郭里奥
26分钟前
0
0
python使用有序字典

python自带的collections包中有很多有用的数据结构可供使用,其中有个叫OrderedDict类,它可以在使用的时候记录元素插入顺序,在遍历使用的时候就可以按照原顺序遍历。 a = {"a":1,"b"...

芝麻糖人
56分钟前
0
0
RestTemplate HttpMessageConverter

RestTemplate 微信接口 text/plain HttpMessageConverter

微小宝
56分钟前
0
0
mysql视图/存储过程/函数/事件/触发器

--语法参考:https://dev.mysql.com/doc/ (当前用的是5.6) https://dev.mysql.com/doc/refman/5.6/en/sql-syntax-data-manipulation.html --视图 CREATE VIEW test.v AS SELECT * FROM t;......

坦途abc
58分钟前
0
0
MySQL参数优化案例

环境介绍 硬件配置 cpu核心数 内存大小 磁盘空间 16核 256G 3T 软件环境 操作系统版本 mysql版本 表数目 单表行数 centos-7.4 mysql-5.7.22 128张表 2kw行 优化层级与指导思想 优化层级 MySQ...

小致dad
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部