图解LeetCode第 445 号问题： 两数相加 II
图解LeetCode第 445 号问题： 两数相加 II
五分钟学算法
发布于 2019-09-03 18:05:33
发布于 2019-09-03 18:05:33
总第64篇/程序员小吴
LeetCode上第 445 号问题：Add Two Numbers II
题目描述
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
思路解析
由于计算时要保证最右边的数对齐，那么很自然的想到先用 栈 存放链表中的每个值，然后依次计算。由于相加时可能产生进位，所以使用一个 flag 表示是否有进位。
提示：若栈中元素相加结束之后仍有进位，则需要新加入一个头结点。
动画演示
动画演示 Made by 王琛
参考代码
class Solution:
def addTwoNumbers(self, l1, l2):
# 分别入栈
stack1 = []
stack2 = []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
flag = 0
head = None
while stack1 or stack2 or flag != 0:
if stack1:
flag += stack1.pop()
if stack2:
flag += stack2.pop()
node = ListNode(flag % 10)
node.next = head
head = node
flag = flag // 10
return head
代码截图
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-01-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录