题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
- 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即 617 + 295
- 输出：2 -> 1 -> 9，即 912
题目思考
- 假设这些数位是正向存放的，又该如何解决呢?
示例：
- 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即 617 + 295
- 输出：9 -> 1 -> 2，即 912
解决方案
思路
- 因为数位是反向存放的, 所以可以直接利用逐位相加: 将每一位进行求和, 如果大于 10 的话进位为 1, 放在下一位继续求和即可
- 特别注意最高位进位为 1 的特殊情况, 比如 99+1. 所以可以将进位是否为 0 也作为循环的条件, 统一起来, 从而避免遗漏, 具体参见下面的代码部分
- 接下来考虑进阶问题: 节点正向存放时怎么解决?
- 很容易想到的思路就是将输入链表进行翻转, 求完和之后再翻转一次, 从而使得最终的和也满足正向存放. 对应下面代码中的 addTwoNumbersInForwardDirection 方法
复杂度
- 时间复杂度 O(M+N): 只需要遍历每个节点一遍
- 空间复杂度 O(max(M,N)): 需要新建一个链表, 其节点数目为 M 或 N 的较大值(也可能多 1, 对应的是最高位进位为 1 的情况). 如果允许修改输入节点的话, 则可以直接在某个链表基础上改值, 从而将空间复杂度降为 O(1)
代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 使用哨兵节点, 作为新的链表头的前一位
dummy = ListNode(0)
cur = dummy
# carry存储当前进位
carry = 0
# 将carry是否为0也作为循环条件, 如果两个链表都遍历完毕但仍有进位时, 也需要进行处理
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
# 求当前位的和, 以及新的进位
carry, sm = divmod(carry, 10)
cur.next = ListNode(sm)
cur = cur.next
return dummy.next
def addTwoNumbersInForwardDirection(self, l1: ListNode,
l2: ListNode) -> ListNode:
# 正向存放的话
# 先转成反向, 然后调用addTwoNumbers, 最后再把结果反过来
def reverse(root):
if not root:
return root
# 经典三指针链表翻转
pre = None
cur = root
while cur:
nex = cur.next
cur.next = pre
pre = cur
cur = nex
return pre
return reverse(self.addTwoNumbers(reverse(l1), reverse(l2))) 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号