LeetCode题目（Python实现）：两数相加

深藏阁楼爱情的钟 2023-07-13 03:23 15阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：新建链表
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  想法二：原地修改
     *   *  执行结果
         *  复杂度分析
     *  递归法
     *   *  执行结果
     *  小结

# 题目 #

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

**示例** :

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

## 想法一：新建链表 ##

### 算法实现 ###

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        cur = head
        while l1 is not None or l2 is not None:
            cur.next = ListNode(0)
            sum = cur.val + (l1.val if l1 is not None else 0) + (l2.val if l2 is not None else 0)
            if sum / 10 >= 1:
                cur.val = sum % 10
                cur.next.val += 1
            else:
                cur.val = sum
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
            if l1 is not None or l2 is not None:
                cur = cur.next
            elif cur.next.val == 0:
                cur.next = None
        return head

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 72 ms, 在所有 Python3 提交中击败了68.80%的用户  
**内存消耗** : 13.7 MB, 在所有 Python3 提交中击败了10.39%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(max(m,n))，  
    我们遍历了两个链表所有节点。
 *  空间复杂度：O(max(m,n))  
    需要额外的n或者m个节点来储存和。

## 想法二：原地修改 ##

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l1
        while True:
            if l1.next is None:
                l1.next = ListNode(0)
            sum = (l1.val if l1 is not None else 0) + (l2.val if l2 is not None else 0)
            if sum / 10 >= 1:
                l1.val = sum % 10
                l1.next.val += 1
            else:
                l1.val = sum
            if l2.next is not None:
                l2 = l2.next
                l1 = l1.next
            elif l1.next.val != 0 or l1.next.next is not None:
                l2.val = 0
                l1 = l1.next
            elif l1.next.val == 0:
                l1.next = None
                break
        return head

### 执行结果 ###

![在这里插入图片描述][20200309235444483.png]

### 复杂度分析 ###

*  时间复杂度：O(max(m,n))，  
    我们遍历了两个链表所有节点。
 *  空间复杂度：O(n)，  
    所需的额外空间取决于L1差L2多少元素。

## 递归法 ##

## 想法二：原地修改法
    ```python
    def add(a, b, carry):
        # 递归的终止条件是a和b都为空
        # 如果carry大于0需要返回一个进位标志
        if not (a or b):
            return ListNode(1) if carry else None
        # 如果a为空则将ListNode(0)赋给a，对于b也是
        a = a if a else ListNode(0)
        b = b if b else ListNode(0)
        # 处理val，以及进位标志
        val = a.val + b.val + carry
        carry = 1 if val >= 10 else 0
        a.val = val % 10
        # 现在a的值就是两个节点相加后的和了
        # 之后再次递归计算a.next和b.next
        a.next = add(a.next, b.next, carry)
        return a
    
    return add(l1, l2, 0)

### 执行结果 ###

![在这里插入图片描述][20200310000404229.png]

## 小结 ##

先按照自己的想法设计，一种是一遍遍历，一边创建新的链表；另一种是直接在l1上修改值，如果不够再加入新的节点。  
递归法没有想到，还是对递归不太熟练。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309222024925.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20200309235444483.png]: https://img-blog.csdnimg.cn/20200309235444483.png
[20200310000404229.png]: https://img-blog.csdnimg.cn/20200310000404229.png