首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-2 两数相加

LeetCode-2 两数相加

作者头像
用户3470542
发布2019-06-26 16:12:49
4380
发布2019-06-26 16:12:49
举报
文章被收录于专栏:算法半岛算法半岛

今天学习第2题两数相加,这个题目特别经典,经常在面试中出现,如果面临秋招或春招的小伙伴们最好在面试前将该题能够手写出来。这个题虽然难度为中等,但理解起来不是很困难,借助正文中的图文分析,相信大家一定能理解并测试通过。

题目描述

给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 注意:您可以假设除了数字0之外,这两个数都不会以0开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)输出:7 -> 0 -> 8原因:342 + 465 = 807

分析

这个题理解起来难度不大,就是将数字从个位数开始将数字放到链表的各个结点上,如下图所示:

然后两个链表的对应位置上的数字相加,将相加的值保存到结果链表中。这里需要注意两个关键点:一是如果两个值相加大于9该怎么办?二是两个链表长度不一致该怎么办?

  • 对于关键点一:我们需要借组一个进位标识 carry,当两数之和大于9时将 carry标识为1,否则表示为0。
  • 对于关键点二:我们以最长链表作为终点,对于较短链表对应位置的数值,我们用0来补齐。

下面分析一个具体实例,该实例包含上述两个关键点,如下图所示:

如上图所示,数字342的链表较短,数字7465的链表较长。当两个数字的第二个结点相加时,它们的和为10,这时就需要进位,即 carry=1,且将个位数保留作为结果链表的值。当较短的链表指向为 null结点时,较长的链表指向的值为7,这需要将较短链表的值设置为0,即结果为0+7。 通过上面分析后,再看看如下 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) {        // 创建结果链表的头节点,默认该节点中的value为-1        ListNode dummy = new ListNode(-1);        ListNode pre = dummy;        // 进位标识carry,默认为0        int carry = 0;        // 遍历链表,当两个链表都为空时,退出        while(l1 != null || l2 != null){            // 判断该节点是否为空,当结点为空时,用0补齐;  // 不为空时,加数即为节点的值            int d1 = (l1 == null) ? 0 : l1.val;            int d2 = (l2 == null) ? 0 : l2.val;            // 对结点求和,注意:求和是需要考虑到进位            int sum = d1 + d2 + carry;            // 更新进位标识            carry = (sum >= 10) ? 1 : 0;            // sum%10标识求和的个位数,将其保存到结果链表中            pre.next = new ListNode(sum % 10);            pre = pre.next;            if(l1 != null) l1 = l1.next;            if(l2 != null) l2 = l2.next;        }
        // 重点,这是一个特殊情况,当两个链表计算完后,        // 还需要判断进位标识是否为1,如果为1,如23+81=104,需要创建一个结点保存最高位        if(carry == 1)            pre.next = new ListNode(1);
        return dummy.next;      }}

对于时间复杂度和空间复杂度,该题都为O(n)。

Github地址

LeetCode-2 两数相加:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A2_AddTwoNumbers.java

参考链接

  • 两数相加:

https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-05-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法半岛 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 分析
  • Github地址
  • 参考链接
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档