文档章节

Leetcode(二):Add Two Numbers

Ambitor
 Ambitor
发布于 2016/04/20 11:37
字数 483
阅读 81
收藏 0

码上生花,ECharts 作品展示赛正式启动!>>>

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
粉丝 75
博文 33
码字总数 33366
作品 0
深圳
技术主管
私信 提问
加载中
请先登录后再评论。
[LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计

Design and implement a TwoSum class. It should support the following operations:add and find. add - Add the number to an internal data structure. find - Find if there exists any......

osc_zrrg1637
2018/02/28
4
0
[LeetCode] 167. Two Sum II - Input array is sorted 两数和 II - 输入是有序的数组

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indic......

osc_zrrg1637
2018/02/28
2
0
[LeetCode] 445. Add Two Numbers II 两个数字相加之二

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers ......

osc_od61rt0p
2018/03/01
2
0
Leetcode——2. 两数相加

难度: 中等 题目 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single......

osc_fzp57c02
2019/06/16
2
0
从已排序数组中求两数和等于输入值TwoSumII167 -leetcode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indic......

woshixin
2018/10/25
16
0

没有更多内容

加载失败,请刷新页面

加载更多

mybatis之foreach用法

在做mybatis的mapper.xml文件的时候,我们时常用到这样的情况:动态生成sql语句的查询条件,这个时候我们就可以用mybatis的foreach了 foreach元素的属性主要有item,index,collection,ope...

osc_0hs26yvj
39分钟前
3
0
css笔记整理

0索引 1html标签块 2选择器 3CSS的引入方式: 4CSS浮动 :流式布局 5盒子模型 6案例一网站首页 7案例二网站注册页面 1html标签块 div标签:默认占- -行,自动换行 span标签:内容显示在同- -行 <!...

osc_3grma05a
40分钟前
5
0
js获取图片的EXIF,解决图片旋转问题

相信大家在做项目的时候会遇到在canvas里加入图片时,图片发生90°,180°的旋转。当时的你肯定时懵逼的,为毛。 其实这就是图片的EXIF搞的鬼。 什么是EXIF 简单来说,Exif 信息就是由数码相...

osc_ytmgp8ea
41分钟前
10
0
StringUtils.isEmpty()和isBlank()的区别

一、概述 两种判断字符串是否为空的用法都是在程序开发时常用的,相信不少同学在这种简单的问题上也吃过亏,到底有什么区别,使用有什么讲究,带着问题往下看。 二、jar包 commons-lang3-3....

osc_1mofhvr6
42分钟前
11
0
H5嵌入钉钉

1,需要在项目种引入钉钉官方的js <script type="text/javascript" src="http://g.alicdn.com/dingding/dingtalk-jsapi/2.3.0/dingtalk.open.js" ></script> 或者npm 也可以的 2,钉钉......

osc_ucqb2u3q
44分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部