LeetCode2: Add two numbers(两数相加)

栏目: 数据库 · 发布时间: 5年前

内容简介:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)输出:7 -> 0 -> 8

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出:7 -> 0 -> 8

输入:(8 -> 4 -> 9) + (5 -> 6 -> 3)

输出:3 -> 1 -> 3 -> 1

解题方法

初等数学

简单的数学相加即可,不过需要处理几个特殊情况,当两个链表长度不同时,短链表下一位数据用0填充

在两个链接相加的过程中,增加一个变量,用于记录低位和像高位的进位情况,在两个链表遍历后,在查看此值,决定是否添加高位.

图解相关思路

这里输入的两个链表分别为8->4->9和5->6->3

LeetCode2: Add two numbers(两数相加)

同时取出两个钟列表的第一个元素,计算sum =13,因为result只记录当前个位数据,通过sum%10得到个位内容,添加到结果链表尾部,同时计算进位标识carry = sum/10 = 1.

LeetCode2: Add two numbers(两数相加)

重复上面步骤,将1插入结果链表尾部,计算carry = 1

LeetCode2: Add two numbers(两数相加)

重复上面步骤,将3插入结果链表尾部,计算carry = 1

LeetCode2: Add two numbers(两数相加)

当L1和L2都遍历结束后,检查carry的内容,发现此时carry非0,则尾插一个carry作为高位的内容

LeetCode2: Add two numbers(两数相加)

代码实现

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode temp = result;
    int carry = 0;

    while (l1 != null || l2 != null) {
        int a = (l1 != null) ? l1.val : 0;
        int b = (l2 != null) ? l2.val : 0;
        int sum = carry + a + b;

        carry = sum / 10;
        temp.next = new ListNode(sum % 10);
        temp = temp.next;

        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }


    if (carry > 0) {
        temp.next = new ListNode(carry);
    }
    return result.next;
}
复制代码

相关代码 欢迎大家关注并提出改进的建议


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

硅谷热

硅谷热

埃弗雷特.M.罗杰斯 / 范国鹰 等 / 1985.8 / 经济科学出版社 / 1.9

《硅谷热》总共分三部分。第一部分为“硅谷的崛起”,以苹果电脑的传奇故事为主线,讲述了硅谷的发展历史。第二部分为“高技术文明”,从风险投资、创业故事、人物传奇等各个方面描绘了硅谷的生态状况。第三部分为“硅谷的明天”,讲述了硅谷模式在全球的扩散、硅谷面临的全球竞争和深远影响。 书中,硅谷这场传奇的主要角色:人物、公司、技术、产品等都综合在其中,一锅子端给了嗷嗷待哺的人们:PC革命、半导体传奇、软......一起来看看 《硅谷热》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具