445. Add Two Numbers II

题目描述和难度

  • 题目描述：

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

 

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

进阶:

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

示例:

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

思路分析

求解关键：使用栈将两个链表逆向存储，然后就可以从个位开始对齐相加、进位

参考解答

参考解答1

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


class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        stack1 = []
        stack2 = []
        p1 = l1
        p2 = l2
        while p1:
            stack1.append(p1.val)
            p1 = p1.next
        while p2:
            stack2.append(p2.val)
            p2 = p2.next
        res = []
        s = 0
        while stack1 or stack2:
            if stack1:
                s += stack1.pop()
            if stack2:
                s += stack2.pop()
            res.append(s % 10)
            s //= 10
        if s == 1:
            res.append(1)
        head = ListNode(res.pop())
        cur_node = head
        while len(res):
            cur_node.next = ListNode(res.pop())
            cur_node = cur_node.next
        return head

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0445-add-two-numbers-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。