[LeetCode] 2. Add Two Numbers 题解

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

内容简介:给你两个假设链表都不会以 0 开头,除了 0 本身外。

给你两个 非空 链表,分别代表两个非负整数,它们的高低位顺序和链表顺序相反,链表中,每个节点代表一位数,要求将两个链表相加,结果也以链表形式返回。

假设链表都不会以 0 开头,除了 0 本身外。

例子:

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 0 -> 8
解释: 342 + 465 = 807.
复制代码

问题难度

Medium

解题思路

这道题虽然标中等难度,但实际上却比较简单,因为链表的顺序和数字的高低位顺序相反,即链表头是低位,而链表尾是高位,所以把两个链表代表的数相加,实际上就是按链表顺序,依次从头(低位)到尾(高位)对两个链表对应的节点做加法操作。所以,这道题的时间复杂度为 。

此外,写程序时还需要注意进位的问题,如果有进位,则需要用一个变量来标记,我们尤其需要注意下面这样的 case:

1
+ 9 -> 9 -> 9
= 0 -> 0 -> 0 -> 1
复制代码

在性能的优化上,我发现如果减少内存分配操作,可以极大的提升运行速度,也就是说,我们可以利用现有链表的节点,将计算结果存储在里面,这样,整个程序基本上不需要创建新节点,你的程序一定可以跑一个好分数:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        ret = last = ListNode(0)
        ret.next = last.next = l1
        while l1 and l2:
            val = l1.val + l2.val + carry
            carry = val / 10
            val = val % 10
            l1.val = val
            
            l2 = l2.next
            last = l1
            l1 = l1.next

        if l2:
            last.next = l2

        l1 = last.next

        while l1:
            val = l1.val + carry
            carry = val / 10
            l1.val = val % 10
            last = l1
            l1 = l1.next

        if carry == 1:
            last.next = ListNode(carry)

        return ret.next
复制代码

原题链接


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

生态战略:设计未来企业新模式

生态战略:设计未来企业新模式

周文艺 / 机械工业出版社 / 2017-3 / 49.00

思想影响战略,战略决定组织。在充满高度不确定性的今天,企业要生存和发展,必须不断进行组织变革与进化,跨越不连续性的鸿沟。本书分析了大量互联网生态型企业的案例,从生态思维进化、生态战略构建和生态组织变革三个角度出发,全面阐述了企业的进化之路。 本书认为,生态是企业进化的核心思想,企业须重新定义增长模式,从封闭的企业链转向开放的价值网,不断创新文化、技术和连接,培育新物种,实现企业从技术生态位到......一起来看看 《生态战略:设计未来企业新模式》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具