您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
在LeetCode的众多算法题中,”两数相加”(Add Two Numbers)是一个经典的链表操作问题。这个问题不仅考察了链表的基本操作,还涉及到了进位处理等细节。本文将通过一个具体的示例,详细分析如何解决这个问题。
给定两个非空的链表,表示两个非负的整数。每个链表中的每个节点存储一个数字,且这些数字是逆序存储的。例如,链表 2 -> 4 -> 3
表示整数 342
。要求将这两个数相加,并以相同的形式返回一个新的链表。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
解释:342 + 465 = 807
要解决这个问题,我们需要模拟两个数的加法过程。具体步骤如下:
carry
为 0。carry
。carry
设置为 1,并将当前节点的值设置为 sum % 10
。carry
相加。carry
仍然为 1,则需要在新链表的末尾添加一个值为 1 的节点。class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
current = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
让我们通过一个具体的示例来详细分析代码的执行过程。
输入:
l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4
执行过程:
初始化:
dummy
节点为 0
,current
指向 dummy
,carry
为 0
。第一次循环:
val1 = 2
,val2 = 5
,total = 2 + 5 + 0 = 7
。carry = 7 // 10 = 0
,current.next = ListNode(7 % 10) = ListNode(7)
。current
移动到 ListNode(7)
。l1
和 l2
分别移动到下一个节点。第二次循环:
val1 = 4
,val2 = 6
,total = 4 + 6 + 0 = 10
。carry = 10 // 10 = 1
,current.next = ListNode(10 % 10) = ListNode(0)
。current
移动到 ListNode(0)
。l1
和 l2
分别移动到下一个节点。第三次循环:
val1 = 3
,val2 = 4
,total = 3 + 4 + 1 = 8
。carry = 8 // 10 = 0
,current.next = ListNode(8 % 10) = ListNode(8)
。current
移动到 ListNode(8)
。l1
和 l2
都为 None
,循环结束。返回结果:
dummy.next
指向 7 -> 0 -> 8
,即结果为 7 -> 0 -> 8
。输出:
7 -> 0 -> 8
通过这个示例分析,我们可以看到,”两数相加”问题的关键在于模拟加法过程,并正确处理进位和链表长度不一致的情况。通过使用一个虚拟头节点 dummy
,我们可以简化链表的操作,避免处理头节点的特殊情况。希望本文的分析能够帮助你更好地理解这个问题,并在LeetCode的练习中取得更好的成绩。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。