图解LeetCode第 445 号问题: 两数相加 II

图解LeetCode第 445 号问题:  两数相加 II

总第64篇/程序员小吴

LeetCode上第 445 号问题:Add Two Numbers II

题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)    
输出: 7 -> 8 -> 0 -> 7

思路解析

由于计算时要保证最右边的数对齐,那么很自然的想到先用 栈 存放链表中的每个值,然后依次计算。由于相加时可能产生进位,所以使用一个 flag 表示是否有进位。

提示:若栈中元素相加结束之后仍有进位,则需要新加入一个头结点。

动画演示

动画演示 Made by 王琛

参考代码

 1class Solution:
2    def addTwoNumbers(self, l1, l2):
3        # 分别入栈
4        stack1 = []
5        stack2 = []
6        while l1:
7            stack1.append(l1.val)
8            l1 = l1.next
9        while l2:
10            stack2.append(l2.val)
11            l2 = l2.next
12
13        flag = 0
14        head = None
15        while stack1 or stack2 or flag != 0:
16            if stack1:
17                flag += stack1.pop()
18            if stack2:
19                flag += stack2.pop()
20            node = ListNode(flag % 10)
21            node.next = head
22            head = node
23            flag = flag // 10
24        return head

代码截图

图解LeetCode第 445 号问题:  两数相加 II


掏空小吴

图解LeetCode第 445 号问题:  两数相加 II

 / 今日问题 / 

今天这两篇文章的动画是小伙伴提供的,大家感觉效果怎么样?


留言格式 —— Day xx : blablabla


往期推荐:

21天,在Github上获取 6300 star


图解LeetCode第 445 号问题:  两数相加 II

欢迎关注这个会做动画的程序员👆

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解LeetCode第 445 号问题: 两数相加 II

我还会在以下平台发布内容

GitHub 哔哩哔哩