当前位置: 首页 > news >正文

【LeetCode 热题 100】2. 两数相加——(解法二)迭代法

Problem: 2. 两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

文章目录

  • 整体思路
  • 完整代码
  • 时空复杂度
        • 时间复杂度:O(max(M, N))
        • 空间复杂度:O(1) (不考虑输出链表)

整体思路

这段代码同样旨在解决 “两数相加” 的链表问题,但它采用的是一种 迭代 的方法,而不是递归。这种迭代实现通常在生产环境中更受欢迎,因为它避免了深度递归可能导致的栈溢出风险,并且在逻辑上更接近我们手动进行竖式加法的方式。

算法的核心思路是模拟一个逐位相加的过程,并用一个指针来构建结果链表。其逻辑步骤如下:

  1. 初始化

    • 哨兵节点 (Sentinel Node):创建一个 dummy 节点。这是一个非常常见的链表技巧。dummy 节点本身不存储任何有效数据,它的 next 指针将指向结果链表的真正头节点。使用它的好处是,可以统一处理链表的创建逻辑,无需为第一个节点的创建编写特殊代码。
    • 尾指针:创建一个 head 指针(在此处,称其为 tailcurrent 可能更直观),并将其初始化为 dummy。这个指针将始终指向结果链表的最后一个节点,用于方便地追加新节点。
    • 进位:初始化一个 carry 变量为 0。
  2. 迭代相加

    • 算法使用一个 while 循环来驱动整个加法过程。
    • 循环条件while (null != l1 || null != l2 || 0 != carry)。这个条件非常关键且全面,它确保了循环会持续进行,直到满足以下所有条件:两个输入链表都已遍历完毕,并且没有剩余的进位需要处理。这优雅地处理了链表长度不同以及最高位产生进位(如 9+1=10)的情况。
    • 在循环内部
      a. 计算当前位总和:将 carry 加上当前 l1l2 节点的值。在相加前,会检查 l1l2 是否为 null,如果不为 null,则加上其值并将指针后移一位。
      b. 创建并追加新节点:用当前总和的个位数(carry % 10)创建一个新节点,并将其链接到结果链表的末尾(head.next = ...)。
      c. 移动尾指针:将 head 指针移动到新创建的节点上(head = head.next),为下一次追加做准备。
      d. 更新进位:计算要带到下一位的进位(carry /= 10),为下一次循环做准备。
  3. 返回结果

    • 循环结束后,dummy 节点的 next 指针就指向了完整的结果链表的头节点。直接返回 dummy.next 即可。

完整代码

/*** Definition for singly-linked list.*/
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {/*** 将两个由链表表示的非负整数相加(迭代版)。* @param l1 第一个数对应的链表* @param l2 第二个数对应的链表* @return 相加结果对应的链表*/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// dummy 是一个哨兵节点,用于简化链表头部的处理逻辑。ListNode dummy = new ListNode();// head 指针用于构建新链表,它始终指向结果链表的最后一个节点。ListNode head = dummy;// carry 用于存储进位。int carry = 0;// 循环条件:只要任意一个链表还有节点,或者还有进位,就继续计算。while (null != l1 || null != l2 || 0 != carry) {// 如果 l1 不为空,将 l1 的值加到 carry 上,并移动 l1 指针。if (null != l1) {carry += l1.val;l1 = l1.next;}// 如果 l2 不为空,将 l2 的值加到 carry 上,并移动 l2 指针。if (null != l2) {carry += l2.val;l2 = l2.next;}// 创建新节点,其值为当前总和的个位数。head.next = new ListNode(carry % 10);// 将 head 指针移动到新创建的节点上。head = head.next;// 更新进位,为下一轮计算做准备。carry /= 10;}// dummy.next 指向的是结果链表的真正头节点。return dummy.next;}
}

时空复杂度

时间复杂度:O(max(M, N))
  1. 循环次数while 循环的执行次数由最长的链表长度决定。如果 l1 的长度是 Ml2 的长度是 N,循环将执行 max(M, N) 次,如果最后还有进位,则再多执行一次。
  2. 每次操作:在循环的每一次迭代中,执行的都是常数时间的加法、取模、除法、指针移动和节点创建操作。

综合分析
算法的时间复杂度与两个链表中较长者的长度成线性关系。因此,时间复杂度为 O(max(M, N))

空间复杂度:O(1) (不考虑输出链表)
  1. 主要存储开销
    • 算法创建了一个新的链表来存储结果。这个新链表的长度是 max(M, N)max(M, N) + 1。在分析中,输出结果所占用的空间通常不计入额外辅助空间
    • 除此之外,算法只使用了 dummy, head, carry 等几个变量。这些变量的数量是固定的,与输入链表的长度无关。

综合分析
算法所需的额外辅助空间是常数级别的。因此,其空间复杂度为 O(1)。这比递归版本的 O(max(M, N))(因为递归栈)要更优。

参考灵神

http://www.lryc.cn/news/584181.html

相关文章:

  • Java代码块
  • HTML应用指南:利用GET请求获取全国永辉超市门店位置信息
  • @RequestBody和@ResponseBody注解的作用
  • html的outline: none;
  • AI进化论06:连接主义的复兴——神经网络的“蛰伏”与“萌动”
  • 【性能测试】jmeter+Linux环境部署和分布式压测,一篇打通...
  • 【科研绘图系列】R语言绘制相关系数图
  • idea安装maven 拉取依赖失败的解决办法
  • AI问答之手机相机专业拍照模式的主要几个参数解释
  • 《PyQt6-3D:开启Python 3D开发新世界》
  • XSS(ctfshow)
  • cpu利用率,系统吞吐量,周转时间,等待时间,响应时间详解(操作系统)
  • 二进制安全-汇编语言-06-包含多个段的程序
  • QBoost 2025版:加速手机性能,提升使用体验
  • pytorch深度学习-Lenet-Minist
  • 从零开始搭建深度学习大厦系列-2.卷积神经网络基础(5-9)
  • 基于 Flutter 的开源文本 TTS 朗读器(支持 Windows/macOS/Android)
  • 从零实现一个GPT 【React + Express】--- 【2】实现对话流和停止生成
  • Flink Exactly Once 和 幂等
  • Spring for Apache Pulsar->Reactive Support->Message Consumption
  • wpf使用webview2显示网页内容(最低兼容.net framework4.5.2)
  • 以太网基础⑤UDP 协议原理与 FPGA 实现
  • 西电考研录取:哪些省份考研上岸西电更容易?
  • websocket的客户端(发送接收json的消息)
  • TCP-与-UDP-协议详解:原理、区别与应用场景全解析
  • 自动驾驶环境感知:天气数据采集与融合技术实战
  • 关键字前跟空格或首字母, 关键字后跟空格或标点符号; 标点符号后面不是必须跟空格;
  • Duplicate cleaner pro 的使用技巧
  • 汽车加气站操作工分类有几种
  • 制作一款打飞机游戏78:游戏选项