2. 两数相加
本帖最后由 Gnomeshgh 于 2025-7-19 14:18 编辑一、题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = , l2 =
输出：
解释：342 + 465 = 807.
示例 2：
输入：l1 = , l2 =
输出：
示例 3：
输入：l1 = , l2 =
输出：
提示：
每个链表中的节点数在范围 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
二、解题思路
（一）暴力解
将链表转换为数字然后相加，最后在取每一个位进行插入链表。
# 链表转为数字
def listNodeToNum(listnode):
# 保存最后的结果
num = 0
# 每次取一个数之后，会扩大十倍
count = 1
# 当链表为None时结束循环
while listnode:
num = num + count * listnode.val
count = count * 10
listnode = listnode.next
return num
# 采用尾插法
def numToListNode(num):
head = ListNode(num % 10)
rear = head
# 去掉个位
num = num // 10
# 当num为0时退出循环
while num:
node = ListNode(num % 10)
rear.next = node
rear = node
# 去掉个位
num = num // 10
return head
class Solution:
def addTwoNumbers(self, l1: Optional, l2: Optional) -> Optional:
# 将链表转为数字
num1 = listNodeToNum(l1)
num2 = listNodeToNum(l2)
# 将数字相加
num2 = num2 + num1
#将数字转为链表
result = numToListNode(num2)
return result
（二）双指针直接相加
两个指针分别指向两个链表的头部，依次取出数值，然后相加，结果取个位将十位进位。依次循环。
将加和的数字进行尾插。
class Solution:
def addTwoNumbers(self, l1: Optional, l2: Optional) -> Optional:
# 保存链表头部，以及当前指针
dummy = curr = ListNode(0)
# 进位标志
carry = 0
# 如果两个链表都为空且进位为0就退出循环
while l1 or l2 or carry:
# 如果链表不为空就取值，为空就赋值为0
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 直接取进位和个位
carry, out = divmod(val1 + val2 + carry, 10)
# 插入链表
curr.next = ListNode(out)
curr = curr.next
# 链表指针后移
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
页:
[1]