【leetcode算法-中等】2. 两数相加
2024-08-26 06:19:17
【题目描述】
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
【解答】
- 解法:遍历链表
将两个链表看作相同长度,长度短的链表补0再相加,比如:123 + 23 = 123 + 023 = 146
初始化一个哑节点
对于这个哑节点可以这么理解:
· 我用的解法是将相加结果放到一个新的链表中,所以我初始化了一个新链表的头节点dummy
· 但是我们需要不断往新链表后面加节点,如果每加一个新的值,就让dummy = dummy.next,那么我们最后虽然完成了加法,却没办法将新链表返回,因为这时候找不到头节点,之前初始化的dummy节点,已经跑到了新链表的尾部
· 所以我们利用哑节点,再在哑节点后加一个用于接受sum的值的当前节点curr,完成加法后,只要返回dummy.next便可
· while循环刚开始那两个if-else判断的意思:如果 l1 = None(因为若上一个循环中 l1 是链表的尾部节点,而在循环的最后令 l1 = l1.next ,所以下一次循环时,l1 为None),那么None节点是不能拥有 self.val 的,所以若当前节点为None,令x = 0即可完成补0操作,这也是为什么要设置x、y来接收 l1.val 和 l2.val 的原因
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) #哑节点,防止头节点丢失
curr = dummy #当前节点
carry = 0 #进位值 while l1 != None or l2 != None:
# x存储 l1.val的值
# y存储 l2.val的值 if l1 == None:
x = 0
else:
x = l1.val
if l2 == None:
y = 0
else:
y = l2.val
sum = x + y + carry
carry = sum // 10
sum = sum % 10 #真正加上的值
curr.next = ListNode(sum)
curr = curr.next
if l1 != None:
l1 = l1.next
if l2 != None:
l2 = l2.next if carry == 1:
curr.next = ListNode(1)
return dummy.next
执行用时 :76 ms, 在所有 python3 提交中击败了83.44%的用户
内存消耗 :12.8 MB, 在所有 python3 提交中击败了99.56%的用户
最新文章
- py-faster-rcnn搭配pycharm使用
- 【Linux】Too many open files
- JQuery学习之jQuery尺寸
- Objective-C:Category
- apache commons-email1.3使用
- [King.yue]Ext.NET相比WebForm的优势
- 我的插件のinput文本框实现宽度自适应
- 201521044091 java 第一周总结
- 201521123038 《Java程序设计》 第十三周学习总结
- Android属性动画完全解析(中),ValueAnimator和ObjectAnimator的高级用法
- Win32 Ime
- linux磁盘大小获取和文件大小获取
- SuperMap iClient for JavaScript image出图
- 终于解决了用JAVA写窗口程序在不同的windows界面下的显示保持一致。
- 2017-2018面向对象程序设计(Java)课程助教工作职责及分工
- JS DOM操作(三) Window.docunment对象——操作属性
- java.sql.SQLException: ORA-00932: 数据类型不一致: 应为 -, 但却获得 CLOB
- BAT-增加JAVA环境变量(WIN764位)
- linux 的yum源
- Linux入门第二天——基本命令入门(上)
热门文章
- C/C++ -- 判断字符串中存在中文
- vue学习--vue项目端口不固定,无法指定问题
- 【实战】Vue全家桶(vue + axios + vue-router + vuex)搭建移动端H5项目
- Why use swap when there is more than enough RAM.
- TripleDES加解密Java、C#、php
- this和super的用法
- Linux虚拟化与容器化
- pycharm 中文乱码
- [Java复习] MQ
- Python之queue模块以及生产消费者模型