描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
Related Topics
- 递归
- 链表
- 数学
👍 7406 👎 0
题解
一开始很想当然写出如下代码
def addTwoNumbers(self, l1, l2):
l_1 = l1[::-1]
l_2 = l2[::-1]
result = int("".join(map(str, l_1))) + int("".join(map(str, l_2)))
return list(map(int, list(str(result))[::-1]))
但是传入实际上是
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
修改版本如下
"""
10:55 AM info
解答成功:
执行耗时:40 ms,击败了98.97% 的Python用户
内存消耗:13.1 MB,击败了64.44% 的Python用户
"""
class Solution(object):
def addTwoNumbers(self, l1, l2):
result = 0
tmp_1 = l1
tmp_2 = l2
times = 0
while tmp_1 is not None or tmp_2 is not None:
if tmp_1:
result += tmp_1.val * 10 ** times
tmp_1 = tmp_1.next if tmp_1.next else None
if tmp_2:
result += tmp_2.val * 10 ** times
tmp_2 = tmp_2.next if tmp_2.next else None
times += 1
result = list(map(int, str(int(result))))[::-1]
ss = ListNode(val=result[0])
t = ss
for idx in range(1, len(result)):
tmp = ListNode(val=result[idx])
t.next = tmp
t = tmp
return ss
再优化一下尽量一次循环
"""
11:24 PM info
解答成功:
执行耗时:40 ms,击败了98.97% 的Python用户
内存消耗:13.2 MB,击败了46.39% 的Python用户
"""
class Solution:
def addTwoNumbers(self, l1, l2):
if l1 is None or (l1.val is 0 and l1.next is None):
return l2
if l2 is None or (l2.val is 0 and l2.next is None):
return l1
head = prev = ListNode(None)
bit = 0
while l1 or l2 or bit:
t_sum = bit + (l1.val if l1 else 0) + (l2.val if l2 else 0)
temp = ListNode(t_sum)
temp.val = t_sum % 10
bit = t_sum // 10
prev.next = temp
prev = prev.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return head.next
