直播截图
题目描述
给定两个用链表表示的整数,每个节点包含一个数位。
这些数位是反向存放的,也就是个位排在链表首部。
编写函数对这两个整数求和,并用链表形式返回结果。
示例:
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
开始解题(python)
def addTwoNumbers(l1, l2):
dummy = ListNode(0) # 创建一个虚拟节点作为新链表的头部
curr = dummy # 用 curr 指针指向当前节点
carry = 0 # 进位值
while l1 or l2:
# 获取 l1 和 l2 当前位置的数位,如果已经达到链表末尾,则为 0
x = l1.val if l1 else 0
y = l2.val if l2 else 0
# 计算当前位置的和,并考虑进位
# 然后取得个位数存入新链表中
sum = x + y + carry
carry = sum // 10
curr.next = ListNode(sum % 10)
curr = curr.next
# 移动到下一个节点
if l1:
l1 = l1.next
if l2:
l2 = l2.next
# 如果最后还有进位,则在新链表的最后添加一个节点
if carry > 0:
curr.next = ListNode(carry)
return dummy.next # 返回新链表的头部
逐步验算
首先,我们有两个输入链表:
l1: 7 -> 1 -> 6
l2: 5 -> 9 -> 2
我们将使用addTwoNumbers函数来将这两个链表相加,并返回结果链表的头部。
创建一个虚拟节点作为新链表的头部:dummy = ListNode(0),这个节点的值暂时没有意义。
创建一个指针 curr,指向当前节点,初始指向虚拟节点:curr = dummy。
创建一个变量 carry 来表示进位值,初始值为 0。
进入循环,直到 l1 和 l2 都遍历完了。
获取 l1 和 l2 当前位置的数位,如果已经达到链表末尾,则为 0。
对于第一次循环,x = 7 (l1.val),y = 5 (l2.val)。
计算当前位置的和,并考虑进位。
sum = x + y + carry = 7 + 5 + 0 = 12,carry = sum // 10 = 12 // 10 = 1。
这里的 sum 为两个数位的和再加上上一次计算的进位。
创建一个新节点,其值为和的个位数。
curr.next = ListNode(sum % 10) = ListNode(12 % 10) = ListNode(2)。
这个节点将会成为新链表的下一个节点,其值为和的个位数。
将 curr 指针移动到下一个节点。
curr = curr.next,这样 curr 指向了新创建的节点。
移动到下一个节点。
注意,如果 l1 或 l2 已经遍历完了,则将对应的指针设置为 None。
对于第一次循环,l1 和 l2 仍然有下一个节点,所以 l1 和 l2 指针分别向后移动一位。
当循环结束后,检查是否还有进位。
如果 carry 大于 0,则在新链表的最后添加一个节点。
carry = 1,所以 curr.next = ListNode(carry) = ListNode(1)。
这个节点的值为进位值,将会成为新链表的最后一个节点。
返回新链表的头部:dummy.next。dummy 是一个虚拟节点,dummy.next 才是真正的链表头部。
所以最后结果为 2 -> 1 -> 9,即912。
实际应用
这个函数可以用于解决两个链表表示的整数相加的问题。实际应用场景包括但不限于以下情况:
高精度整数相加:当两个整数的位数很大时,常规的整数相加操作可能会造成溢出。使用链表表示整数可以避免溢出问题,并且能够处理任意长的整数相加。
大数计算:在某些科学计算、金融计算或密码学等领域中,可能需要进行大数计算,即超过计算机数据类型范围的数值计算。链表的灵活性使得可以轻松处理大数计算问题。
数据结构的相加:当涉及到两个链表或其他数据结构的相加时,可以使用类似的思路。通过遍历两个数据结构,并将对应位置的元素相加,可以得到新的数据结构。
总之,这个函数提供了一种通用的方法,用于解决链表或其他数据结构中表示的数字相加的问题,可以应用于多种实际场景中。