1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 445. 两数相加 II

flypython • • leetcode题解

445. 两数相加 II

链接：https://leetcode-cn.com/problems/add-two-numbers-ii/
难度：中等

题目

点击原文链接跳转查看题目

思路

这道题要注意的是，相加的顺序是从链表末尾开始，低位到高位，所以是逆序的。

处理逆序的情况，我们可以翻转链表，也可以借助额外的数据结构。

在题目进阶中，要求输入的链表不能修改，所以我们需要借助额外的数据结构。

如果我们使用栈把两个链接的数字都压住栈中，然后出栈之后相加，这样就解决了。

代码见解决方案

方案代码

解决方案：

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        
        ans = None
        current = 0
        while s1 or s2 or current != 0:
            a = 0 if not s1 else s1.pop()
            b = 0 if not s2 else s2.pop()
            v = a + b + current
            current = v // 10
            v %= 10
            curnode = ListNode(v)
            curnode.next = ans
            ans = curnode
        return ans

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/327.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 13/04/2020 10:50
下一篇 » 15/04/2020 10:54

相关推荐