02：两数相加

题目描述

题目给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

YrzPix

提示

每个链表中的节点数在范围 [1, 100] 内
0 ≤ Node.val ≤ 9
题目数据保证列表表示的数字不含前导零

导入和定义

导入 Optional和定义 NodeList

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

数据结构说明

Optional 类型

Optional 是 Python 类型提示中的一个泛型类型，用于表示一个值可能为 None。在本题中，它用于表示链表节点可能不存在的情况。

# Optional[ListNode] 表示参数可能是 ListNode 类型，也可能是 None
def some_function(node: Optional[ListNode]) -> Optional[ListNode]:
    pass

ListNode 类

ListNode 是一个自定义的链表节点类，用于构建单向链表数据结构：

val: 存储节点的值(0-9)
next: 指向下一个节点的指针

解题思路

同时遍历两个链表，对应位置数字相加
处理进位情况
注意链表长度不同的情况
最后的进位需要新建节点

代码实现


from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], 
                      l2: Optional[ListNode]) -> Optional[ListNode]:
        def to_str(node):
            """
            将一个链表转换成字符串
            """
            num_str = ''
            while node:
                num_str = str(node.val) + num_str
                node = node.next
            return num_str
        
        l1str = to_str(l1)
        l2str = to_str(l2)

        result_sum = int(l1str) + int(l2str)
        prev_node = None

        for digit in str(result_sum):
            node = ListNode(int(digit), prev_node)
            prev_node = node

        return prev_node if prev_node else ListNode(0)

l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))
res = Solution.addTwoNumbers(Solution,l1,l2)

def print_list(node):
    while node:
        print(node.val, end=" ")
        node = node.next
    print()
    
print_list(res)

复杂度分析

时间复杂度：O(max(N,M))，其中 N 和 M 分别为两个链表的长度
空间复杂度：O(max(N,M))，需要存储新链表

代码说明

to_str()函数解释

to_str 函数的目的是将一个链表转换成字符串。在链表中，每个节点包含一个数字和一个指向下一个节点的指针（或链接）。这种数据结构不像数组那样可以直接通过索引访问每个元素，而是需要从头节点开始，通过节点之间的链接逐个遍历。

假设有一个链表，代表数字 807，但是它的表示形式是 7 -> 0 -> 8（头节点是 7，它是数字的最低位）。

函数实现细节

def to_str(node):
    num_str = ''
    while node:
        num_str = str(node.val) + num_str
        node = node.next
    return num_str

工作流程

初始化一个空字符串 num_str：这将用来构建链表代表的数字的字符串表示。
遍历链表：使用 while node: 循环遍历链表。在每次迭代中，node 是当前的链表节点。
构建字符串：在每次迭代中，我们取出当前节点的值 node.val（一个数字），将其转换为字符串，然后将其添加到 num_str 的前面。这是因为我们是从链表的头部开始遍历的，头部是数字的最低位。
移动到下一个节点：通过 node = node.next 移动到链表的下一个节点。
返回结果字符串：一旦遍历完整个链表，num_str 就包含了链表表示的完整数字的字符串形式。这时函数返回 num_str。

示例说明

对于链表 7 -> 0 -> 8：

初始: num_str = ""
第一次迭代: num_str = "7"
第二次迭代: num_str = "07"
第三次迭代: num_str = "807"

最终返回字符串 "807"，实现了链表到数字的正确转换。