LeetCode 刷题:2. 两数相加
2023-02-18 08:41:22
# 算法题
第二题不算太难,思路还是比较好想的,不过写起来稍微有点麻烦,需要注意细节
标题 | 两数相加 |
---|---|
序号 | NO.2 |
难度 | 中等 |
标签 | 递归 链表 数学 |
1. 题目
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4] |
示例 2:
输入:l1 = [0], l2 = [0] |
示例 3:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] |
提示:
- 每个链表中的节点数在范围
[1, 100]
内 - 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 代码
看到这题,思路首先有两个。
从后往前读取这个数,然后将两数相加,再将结果倒过来插到链表中,这个方法更符合人们的直观思想
根据数学两数相加的原理,依次按个位十位百位相加,最后得到结果,这道题正好用到了这个原理,该计算个位相加,插到链表中,再计算十位百位・・・・・・,注意判断两数位数不等以及两数相加后位数多一位的情况。如
99 + 9 = 108
显然,第二种方法比第一种方法好很多,故采用第二种方法。
时间复杂度 O (n)
空间复杂度 O (n)
执行用时:3324ms
内存消耗:15.6MB
1 | # Definition for singly-linked list. |
- 执行用时:8ms
- 内存消耗:7.4MB
1 | /** |