Python链表之两数之和
Python链表之两数之和
公众号guangcity
发布于 2019-09-20 11:43:09
发布于 2019-09-20 11:43:09
两数之和
【今日知图】 标记 某一块代码可能需要稍后处理 使用m增加一个标记，标记名称可以是a~z和A~Z之间的任意一个字母; 添加标记了的行如果被删除，标记同时被删除; 后面的标记名与前面一致会覆盖前面相同的标记;
mx mark 添加标记x，x可以是a~z和A~Z之间的任意一个字母
'x 直接定位到标记x所在位置
0.说在前面1.两数之和2.思路分析3.实现方法4.算法分析5.作者的话
0.说在前面
又到了新的一周，我们这周的第一篇LeetCode，有关链表话题，在python中如何操作链表，定义链表呢？有关这个问题，大家可以留言，将情况反馈，我根据情况发文，本来惯例周二发文，实际上是每周一刷题，但是由于时间安排问题放在了周二，所以以后还是惯例周二，但是本周二被安排了，所以提前发文LeetCode！
下面一起来看本次刷题，两数之和！！！
1.两数之和
问题
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 单位 数字。
如果，我们将这两个数起来相加起来，则会返回出一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
2.思路分析
【方法一】
将l1链表的数取出，组成一个数，l2同理，最终求和，将求和结果循环得出每个节点的值，然后链表连接即可！！！
【方法二】
边循环max(len(l1)，len(l1))，边求和，边插入新链表数！！！
3.实现方法
【方法一】
def addTwoNumbers(self, l1, l2):
sum_l1 = 0
muti = 1
while l1:
sum_l1 += l1.val*muti
l1=l1.next
muti*=10
sum_l2 = 0
muti = 1
while l2:
sum_l2 += l2.val*muti
l2=l2.next
muti*=10
sum_res = sum_l1+sum_l2
print(sum_res)
l = ListNode(0)
p = l
if not sum_res:
return [0]
while sum_res!=0:
r = sum_res%10
sum_res = sum_res//10
p.next = ListNode(r)
p = p.next
p.next = None
p=l.next
del l
return p
【方法二】
def addTwoNumbers(self, l1, l2):
if not l1:
return l2
if not l2:
return l1
up = 0
head = ListNode(0)
p = head
while l1 or l2:
curr_sum = 0
if l1:
curr_sum+=l1.val
l1=l1.next
if l2:
curr_sum+=l2.val
l2=l2.next
curr_val = (curr_sum+up)%10
up = (curr_sum+up)//10
p.next = ListNode(curr_val)
p=p.next
if up:
p.next = ListNode(1)
p=p.next
p.next = None
p = head.next
del head
return p
4.算法分析
方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
算法一 | O(n) | O(n) |
算法二 | O(n) | O(n) |
对比发现两者时间复杂度与空间复杂度一致，那为什么还会有这么大的提交结果差异？
原因在于，第一个算法有三个循环，虽然都是O(n)，但是耗时三倍！！！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录