Python链表之两数之和
- 2019 年 10 月 5 日
- 笔记
两数之和
【今日知图】 标记 某一块代码可能需要稍后处理 使用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)，但是耗时三倍！！！
