LeetCode中两数相加的示例分析

发布时间:2021-12-15 14:33:44 作者:小新
来源:亿速云 阅读:154

LeetCode中两数相加的示例分析

在LeetCode的众多算法题中,”两数相加”(Add Two Numbers)是一个经典的链表操作问题。这个问题不仅考察了链表的基本操作,还涉及到了进位处理等细节。本文将通过一个具体的示例,详细分析如何解决这个问题。

问题描述

给定两个非空的链表,表示两个非负的整数。每个链表中的每个节点存储一个数字,且这些数字是逆序存储的。例如,链表 2 -> 4 -> 3 表示整数 342。要求将这两个数相加,并以相同的形式返回一个新的链表。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
解释:342 + 465 = 807

解题思路

要解决这个问题,我们需要模拟两个数的加法过程。具体步骤如下:

  1. 初始化:创建一个新的链表来存储结果,并初始化一个进位变量 carry 为 0。
  2. 遍历链表:同时遍历两个链表,将对应节点的值相加,并加上进位 carry
  3. 处理进位:如果相加的结果大于等于 10,则需要进位,将 carry 设置为 1,并将当前节点的值设置为 sum % 10
  4. 处理链表长度不一致的情况:如果两个链表的长度不一致,较短的链表在遍历结束后,剩余的节点值需要与 carry 相加。
  5. 处理最后的进位:如果遍历结束后,carry 仍然为 1,则需要在新链表的末尾添加一个值为 1 的节点。
  6. 返回结果:返回新链表的头节点。

代码实现

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

执行过程:

  1. 初始化

    • dummy 节点为 0current 指向 dummycarry0
  2. 第一次循环

    • val1 = 2val2 = 5total = 2 + 5 + 0 = 7
    • carry = 7 // 10 = 0current.next = ListNode(7 % 10) = ListNode(7)
    • current 移动到 ListNode(7)
    • l1l2 分别移动到下一个节点。
  3. 第二次循环

    • val1 = 4val2 = 6total = 4 + 6 + 0 = 10
    • carry = 10 // 10 = 1current.next = ListNode(10 % 10) = ListNode(0)
    • current 移动到 ListNode(0)
    • l1l2 分别移动到下一个节点。
  4. 第三次循环

    • val1 = 3val2 = 4total = 3 + 4 + 1 = 8
    • carry = 8 // 10 = 0current.next = ListNode(8 % 10) = ListNode(8)
    • current 移动到 ListNode(8)
    • l1l2 都为 None,循环结束。
  5. 返回结果

    • dummy.next 指向 7 -> 0 -> 8,即结果为 7 -> 0 -> 8

输出:

7 -> 0 -> 8

复杂度分析

总结

通过这个示例分析,我们可以看到,”两数相加”问题的关键在于模拟加法过程,并正确处理进位和链表长度不一致的情况。通过使用一个虚拟头节点 dummy,我们可以简化链表的操作,避免处理头节点的特殊情况。希望本文的分析能够帮助你更好地理解这个问题,并在LeetCode的练习中取得更好的成绩。

推荐阅读:
  1. Python怎么实现两数相加
  2. LeetCode如何实现两数之和

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:leetcode怎么计算等价多米诺骨牌对的数量

下一篇:LeetCode如何求平方数之和

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》