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

【LeetCode 热题 100】21. 合并两个有序链表——(解法二)递归法

Problem: 21. 合并两个有序链表
题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

【LeetCode 热题 100】21. 合并两个有序链表——(解法一)迭代法

文章目录

  • 整体思路
  • 完整代码
  • 时空复杂度
    • 时间复杂度:O(M + N)
        • 空间复杂度:O(M + N)

整体思路

这段代码同样旨在解决 “合并两个有序链表” 的问题。与上一个迭代版本不同,此版本采用了一种非常优雅和简洁的 递归(Recursion) 方式来实现。

算法的核心思想是:将“合并两个链表”的大问题,分解为“确定当前最小节点,并将其链接到剩余部分合并结果”的子问题

  1. 递归的终止条件(Base Case)

    • 递归必须有明确的终止条件,以防止无限循环。
    • if (null == list1): 如果第一个链表为空,那么合并的结果就是第二个链表本身。直接返回 list2
    • if (null == list2): 同理,如果第二个链表为空,合并的结果就是第一个链表。直接返回 list1
    • 这两个条件是递归的“出口”。
  2. 递归的递推关系(Recursive Step)

    • 当两个链表都不为空时,需要比较它们的头节点 list1.vallist2.val
    • Case 1: list1.val < list2.val
      • 这说明在当前这一步,list1 的头节点是两个链表所有剩余节点中最小的。
      • 因此,最终合并后的链表的头节点就是 list1
      • 那么 list1next 应该指向谁呢?它应该指向 list1.nextlist2 这两个子链表合并后的结果
      • 于是,我们进行一次递归调用 mergeTwoLists(list1.next, list2),并将返回的结果赋给 list1.next
      • 最后,返回 list1 作为这一层递归的结果。
    • Case 2: list1.val >= list2.val
      • 这说明 list2 的头节点更小(或相等)。
      • 因此,最终合并后的链表的头节点是 list2
      • 同理,list2next 应该指向 list1list2.next 这两个子链表合并后的结果
      • 进行递归调用 mergeTwoLists(list1, list2.next),并将结果赋给 list2.next
      • 返回 list2

通过这种自顶向下的分解和自底向上的构建,递归函数优雅地完成了整个链表的合并。每一层递归都负责确定一个节点的位置,并将其链接到下一层返回的已合并好的子链表上。

完整代码

/*** Definition for singly-linked list.* public 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 list1 第一个有序链表的头节点* @param list2 第二个有序链表的头节点* @return 合并后新链表的头节点*/public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 递归终止条件 1: 如果 list1 为空,则合并结果就是 list2if (null == list1) {return list2;}// 递归终止条件 2: 如果 list2 为空,则合并结果就是 list1if (null == list2) {return list1;}// 递归的递推步骤// 比较两个链表的头节点if (list1.val < list2.val) {// 如果 list1 的头节点更小,那么它就是合并后链表的头。// 它的下一个节点是 list1.next 和 list2 合并后的结果。list1.next = mergeTwoLists(list1.next, list2);// 返回 list1 作为当前层合并的结果return list1;} else {// 如果 list2 的头节点更小或相等,那么它就是合并后链表的头。// 它的下一个节点是 list1 和 list2.next 合并后的结果。list2.next = mergeTwoLists(list1, list2.next);// 返回 list2 作为当前层合并的结果return list2;}}
}

时空复杂度

时间复杂度:O(M + N)

  1. 递归调用分析
    • 每一次递归调用都会从 list1list2 中“消耗”掉一个节点。
    • 要将两个链表的所有节点都处理完,总共需要进行 M + N 次递归调用,其中 MN 分别是两个链表的长度。
    • 每次递归调用内部的操作(比较、赋值)都是 O(1) 的。

综合分析
算法的时间复杂度与两个链表的总长度成线性关系,即 O(M + N)

空间复杂度:O(M + N)
  1. 主要存储开销:该算法的主要额外空间开销来自于递归调用栈(Call Stack)
  2. 递归深度
    • 每进行一次递归调用,就会在调用栈上创建一个新的栈帧(stack frame)来存储该次调用的局部变量和返回地址。
    • 递归的深度取决于两个链表被“消耗”完需要多少步。在最坏的情况下,例如一个链表很长而另一个很短,递归会一直深入到长链表的末尾。
    • 因此,递归栈的最大深度等于两个链表长度之和,即 M + N

综合分析
算法所需的额外空间主要由递归调用栈决定。因此,其空间复杂度为 O(M + N)。与迭代法 O(1) 的空间复杂度相比,递归法在空间上效率较低。

参考灵神

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

相关文章:

  • Spark流水线数据对比组件
  • 第6章应用题
  • 01-elasticsearch-搭个简单的window服务-ik分词器-简单使用
  • 【01】MFC入门到精通—— MFC新建基于对话框的项目 介绍(工作界面、资源视图 、类视图)
  • 【前端】ikun-markdown: 纯js实现markdown到富文本html的转换库
  • Java SE 实现简单的图书管理系统(完善菜单操作)
  • 【DOCKER】-3 数据持久化
  • 项目进度受制于资源分配,如何动态调配资源
  • 20250709: WSL+Pycharm 搭建 Python 开发环境
  • PHP 基于模板动态生成 Word 文档:图片 + 表格数据填充全方案(PHPOffice 实战)
  • 爬虫-数据解析
  • 20-C#构造函数--虚方法
  • 机器视觉之工业相机讲解
  • 【leetcode100】下一个排列
  • 题解:P13017 [GESP202506 七级] 线图
  • RAC-CELL(小区)处理
  • 射频前端的革新力量:ATR2057超低噪声放大器深度解析
  • C#基础篇(10)集合类之列表
  • AMIS全栈低代码开发
  • Claude Code 开发使用技巧
  • 一天一道Sql题(day05)
  • 双立柱式带锯床cad【1张总图】+设计说明书+绛重
  • MS32C001-C单片机,32位ARM M0+内核,宽电压、低功耗、小封装。
  • Python PyDub详解:音频处理从未如此简单
  • 高效集成-C#全能打印报表设计器诞生记
  • Paimon 原子提交实现
  • 无人机雷达模块运行与技术解析
  • 【RK3568+PG2L50H开发板实验例程】FPGA部分 | ROM、RAM、FIFO 的使用
  • UI前端与数字孪生结合实践探索:智慧物流的仓储优化与管理系统
  • 缓存三大问题详解与工业级解决方案