02：两数相加
题目描述
题目 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
提示
- 每个链表中的节点数在范围 [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]:
passListNode 类
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"，实现了链表到数字的正确转换。