445. 两数相加 II

https://leetcode-cn.com/problems/add-two-numbers-ii/

解法一：栈

与2.两数相加顺序相反，因此考虑用栈

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
        Head = ListNode(0)    #新链辅助头
        upgrade = 0     #进位
        while len(s1) > 0 and len(s2) > 0:
            sum = s1.pop() + s2.pop() + upgrade
            node = ListNode(sum%10)
            upgrade = sum // 10
            node.next = Head.next   #头插
            Head.next = node
        #若栈1还有剩
        while len(s1) > 0:  
            sum = s1.pop() + upgrade
            node = ListNode(sum%10)
            upgrade = sum // 10
            node.next = Head.next
            Head.next = node
        #若栈2还有剩
        while len(s2) > 0:  
            sum = s2.pop() + upgrade
            node = ListNode(sum%10)
            upgrade = sum // 10
            node.next = Head.next
            Head.next = node
        #若还有进位
        if upgrade != 0:
            node = ListNode(upgrade)
            node.next = Head.next
            Head.next = node
        return Head.next            

解法二：将链表转为数字再相加

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def list2str(l):    #函数，链表转字符串
            res = ''
            while l:
                res += str(l.val)
                l = l.next
            return res
        sum = int(list2str(l1)) + int(list2str(l2))    #两数相加
        
        Head = ListNode(None)    #辅助头
        i = Head
        for ch in str(sum):    #用求和结果的每一位，构造新链
            i.next = ListNode(int(ch))
            i = i.next
        return Head.next