【LeetCode】2. 两数相加（链表逆序存储——易） & 445. 两数相加 II（链表正序存储——难：栈）

两数相加（链表逆序存储——易）

一、题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

二、解题思路 & 代码

# 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:
        pre = ListNode(0)  # 新建节点 0 
        cur = pre          # cur 和 pre 都指向新建节点 0
        carry = 0          # 进位为 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = carry + x + y
            carry = s // 10
            s = s % 10
            cur.next = ListNode(s)  # 新建节点
            cur = cur.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        if carry > 0:
            cur.next = ListNode(1)
        return pre.next

复杂度分析

1. 时间复杂度：$O(max(m,n))$，假设 m 和 n 分别表示 $l1$ 和 $l2$ 的长度，上面的算法最多重复$max(m,n)$ 次。

2. 空间复杂度：$O(max(m,n))$， 新列表的长度最多为 $max(m,n)+1$。

###################################################################################################################################################################################################

两数相加 II（链表正序存储——难：栈）

1. 题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

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

二、解题思路 & 代码

本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：

把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。

# 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:
        stack1 = []
        stack2 = []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        ans = None
        carry = 0
        while stack1 or stack2 or carry != 0:
            x = stack1.pop() if stack1 else 0
            y = stack2.pop() if stack2 else 0
            s = carry + x + y
            carry = s // 10
            s = s % 10
            cur = ListNode(s)  
            cur.next = ans
            ans = cur
        return ans

复杂度分析

1. 时间复杂度：$O(max(m,n))$，其中 m 与 n 分别为两个链表的长度。我们需要遍历每个链表。

2. 空间复杂度：$O(m+n)$，其中 m 与 n 分别为两个链表的长度。这是我们把链表内容放入栈中所用的空间。

参考：

1. LeetCode题解
2. leetCode官方题解

本文地址：https://blog.csdn.net/weixin_41888257/article/details/107289086