[LeetCode-py-0002] Add Two Numbers

原文

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

翻译

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

分析

先定义节点类:

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

方法一

最笨的方法就是, 把每个链表分别求出对应代表的非负整数, 然后求和, 最后把结果再转换为倒序链表;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def addTwoNumbers1(self, l1: ListNode, l2: ListNode) -> ListNode:
n = 0
index = 1
cur = l1
while cur is not None:
n += cur.val * index
index *= 10
cur = cur.next
cur = l2
index = 1
while cur is not None:
n += cur.val * index
index *= 10
cur = cur.next
res = ListNode(0)
cur = res
while n > 0:
n, cur.val = divmod(n, 10)
if n > 0:
cur.next = ListNode(0)
cur = cur.next
return res

链表转整数, 是依次乘以 $10^n$, n 表示链表索引, 并累加;
整数转链表则是依次除以 10, 每次余数即为链表对应值, 整数部分继续按前面的操作;

方法二

按照人计算习惯, 对两个链表进行逐位求和, 并除以 10 求整数部分和余数部分, 余数部分即为本位值, 整数部分则为进位值, 在下一位计算时优先加上进位值;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def addTwoNumbers2(self, l1: ListNode, l2: ListNode) -> ListNode:
cur1 = l1
cur2 = l2
n = 0
cur = res = ListNode(0)
while True:
cur.val += n
if cur1 is not None:
cur.val += cur1.val
cur1 = cur1.next
if cur2 is not None:
cur.val += cur2.val
cur2 = cur2.next
n, cur.val = divmod(cur.val, 10)
if n > 0 or cur1 is not None or cur2 is not None:
cur.next = ListNode(0)
cur = cur.next
else:
break
return res

方法三

采用递归的方式, 实际上是将方法二的循环转换为递归实现;
其中需要注意的一点是, 如果存在进位情况, 要先将进位值 n 作为链表, 加到其中一个子链表中;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def addTwoNumbers3(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
if l1 is not None:
res.val += l1.val
if l2 is not None:
res.val += l2.val
n, res.val = divmod(res.val, 10)
next_l1 = None if l1 is None else l1.next
next_l2 = None if l2 is None else l2.next
if n > 0:
next_l1 = self.addTwoNumbers3(ListNode(n), next_l1)
if next_l1 is not None or next_l2 is not None:
res.next = self.addTwoNumbers3(next_l1, next_l2)
return res

方法四

与方法二一样, 只是美化了一下实现;
代码中直接使用两个参数指针, 只初始化了一个结果指针;
而且将对进位值(0/1)的判断, 移到下一轮循环中(val1+val2+carry)直接相加, 不用再进行判断;

1
2
3
4
5
6
7
8
9
10
11
12
13
def addTwoNumbers4(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
res_cur = res
carry = 0
while l1 or l2 or carry:
val1 = (l1.val if l1 else 0)
val2 = (l2.val if l2 else 0)
carry, out = divmod(val1 + val2 + carry, 10)
res_cur.next = ListNode(out)
res_cur = res_cur.next
l1 = (l1.next if l1 else None)
l2 = (l2.next if l2 else None)
return res.next

对比

方法时间复杂度空间复杂度
方法一$O(m + n + max(m,n))$$O(max(m,n))$
方法二$O(max(m,n))$$O(max(m,n))$
方法三$O(max(m,n))$$O(max(m,n))$
方法四$O(max(m,n))$$O(max(m,n))$

代码

LeetCode-py


--------------------本文至此结束  感谢您的阅读--------------------

本文标题:[LeetCode-py-0002] Add Two Numbers

文章作者:Memento

发布时间:2019年04月24日 - 19:04

最后更新:2019年04月24日 - 21:04

原始链接:https://memento.net.cn/post/ef888847.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Memento wechat
欢迎您扫一扫上面的微信公众号, 订阅阁主公众号!
坚持原创技术分享, 您的支持将鼓励我继续创作