文档章节

Leetcode(二):Add Two Numbers

Ambitor
 Ambitor
发布于 2016/04/20 11:37
字数 483
阅读 55
收藏 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 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: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
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

没有更多内容

加载失败,请刷新页面

加载更多

SSO单点登录PHP简单版

  前面做了一个新项目,需要用户资源可以需要共享。由于之前没有做过这样的东西,回家之后,立马网站百度“单点登录”。帖子很多,甄别之后,这里列几篇认为比较有营养。   http://blog...

slagga
31分钟前
1
0
Java 泛型详解-绝对是对泛型方法讲解最详细的,没有之一

对java的泛型特性的了解仅限于表面的浅浅一层,直到在学习设计模式时发现有不了解的用法,才想起详细的记录一下。 本文参考java 泛型详解、Java中的泛型方法、 java泛型详解 1 概述 泛型在j...

hensemlee
34分钟前
1
0
Annotation注解详细介绍

目录介绍 1.Annotation库的简单介绍 2.@Nullable和@NonNull 3.资源类型注释 4.类型定义注释 5.线程注释 6.RGB颜色纸注释 7.值范围注释 8.权限注释 9.重写函数注释 10.返回值注释 11.@Keep注释...

潇湘剑雨
36分钟前
1
0
一步步编写自己的PHP爬取代理IP项目(二)

这一章节我们正式开展我们的爬虫项目,首先我们先要知道哪个网站能获取到免费代理IP,目前比较火的有西刺代理,快代理等,这里我们拿西刺代理作为例子。 这里就是一个个免费的IP地址以及各自...

NateHuang
55分钟前
2
0
11-利用思维导图梳理JavaSE-Java的反射机制

11-利用思维导图梳理JavaSE-Java的反射机制 主要内容 1.反射与Class类 1.1.反射概念 1.2.Class类 1.3.实例化Class类 1.4.反射的作用 1.5.Class对象的作用 2.反射的深入应用 2.1.调用无参的成...

飞鱼说编程
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部