两数相加（LeetCode）
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
解题
- 遍历链表：同时遍历两个链表，逐位相加。
- 处理进位：如果两位数字相加的和大于等于10，需要处理进位。
- 构建新链表：将每一位的和（取个位）存入新的链表节点中。
- 处理链表长度不同：如果一个链表比另一个链表短，需要继续处理剩下的部分。
- 处理最终进位：如果最后还有进位，需要在新链表的最后添加一个节点。
# 创建链表节点类
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value # 节点存储的值
self.next = next_node # 下一个节点的引用
def addTwoNumbers(list1, list2):
dummy_head = ListNode(0) # 创建哑节点（虚拟头节点）
current_node = dummy_head # 当前处理的节点
carry_over = 0 # 初始化进位为0
# 遍历两个链表
while list1 is not None or list2 is not None:
# 如果当前节点为空，节点值为0
value1 = list1.value if list1 is not None else 0
value2 = list2.value if list2 is not None else 0
# 计算两个节点的和及进位
total_sum = carry_over + value1 + value2
carry_over = total_sum // 10 # 计算进位
current_node.next = ListNode(total_sum % 10) # 创建新的节点存储当前位的结果
current_node = current_node.next
# 移动到下一个节点
if list1 is not None: list1 = list1.next
if list2 is not None: list2 = list2.next
# 检查最后的进位
if carry_over > 0:
current_node.next = ListNode(carry_over)
return dummy_head.next # 返回结果链表的头节点（哑节点的下一个节点）
# 示例用法
# l1: 2 -> 4 -> 3 (表示数字 342)
# l2: 5 -> 6 -> 4 (表示数字 465)
# 输出: 7 -> 0 -> 8 (表示数字 807)
l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))
result = addTwoNumbers(l1, l2)
# 输出结果链表
while result:
print(result.value, end=' ')
result = result.next
# 输出: 7 0 8
7 0 8
总结
名词解释
链表（Linked List）
- 链表是一种数据结构，其中每个元素（称为节点）包含一个值和一个指向下一个节点的引用（或指针）。
- 在单向链表中，每个节点只指向下一个节点，最后一个节点指向
None，表示链表的结束。节点（Node）
- 节点是链表中的基本组成单位，每个节点包含两个部分：
- 值（
val）：存储的数据。- 引用（
next）：指向下一个节点的指针。哑节点（Dummy Node）
- 哑节点是一个虚拟节点，不存储有效数据，仅用于简化链表的操作，如在链表开头插入新节点或简化链表的遍历。
- 哑节点常常作为链表的头节点，最后返回哑节点的下一个节点作为链表的实际头节点。
进位（Carry）
- 进位是指在数字相加时，当一位的和超过基数（例如十进制数中超过 9）时，将多出的部分传递到下一位。
- 在本例中，两个个位数相加如果大于或等于 10，需要将 10 的倍数作为进位传递到下一位。
初始化（Initialization）
- 初始化是指在使用变量或对象之前，将其设置为一个已知的初始状态或初始值。
- 例如，
carry变量初始化为0，表示没有进位。遍历（Traversal）
- 遍历是指依次访问数据结构中的每个元素。
- 在本例中，遍历链表是指从头节点开始，逐个访问每个节点，直到访问到链表的末尾（
None）。引用（Reference）
- 引用是一个变量，它指向另一变量或对象的内存地址。
- 在链表中，节点的
next属性是一个引用，指向下一个节点。
- 理解链表的结构，如何遍历、插入节点、创建新节点。
- 使用哑节点（dummy node）技巧简化链表操作。
- 处理两个数字的逐位相加，包括进位（carry）的计算。
- 同时遍历两个链表，处理不同长度链表的情况。
原文地址：https://blog.csdn.net/weixin_74254879/article/details/140625442
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！