算法训练 第二周

二、反转链表

在这里插入图片描述
本题给我们了一个单链表的头节点head,要求我们把这个单链表的连接顺序进行逆置,并返回逆置后的链表头节点。

1.头插法

我们需要先创建一个新的头节点ph,然后遍历给出的单链表,把遍历到的每一个节点用头插法接到ph的后面,这样我们就可以得到一个反转后的链表了,最后返回ph的next即可。需要注意的是,在进行头插语句之前,我们需要把当前节点的下一个节点先存储起来,否则会导致遍历节点的next丢失,具体代码如下:

/*** 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 {public ListNode reverseList(ListNode head) {if(head == null) {return null;}ListNode ph = new ListNode();ListNode p = head;ListNode n;while(p != null) {n = p.next;p.next = ph.next;ph.next = p;p = n;}return ph.next;}
}

复杂度分析

  • 时间复杂度:O(n),只需遍历一遍原链表即可。
  • 空间复杂度:O(1)。

2.递归

递归法的要点在于我们需要先假设我们要处理的这个节点之前的节点已经全部完成反转,然后对于这个节点,我们只需要将它的next指向它的上一个节点即可,或者说我们需要将指针指向的节点的next的next指向这个节点本身,具体代码如下:

/*** 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 {public ListNode reverseList(ListNode head) {if(head == null) {return null;}if(head.next == null) {return head;}ListNode prev = head.next;ListNode p = prev.next; head.next.next = head;head.next = null;return process(prev,p);}public ListNode process(ListNode prev,ListNode p) {if(p == null) {return prev;}if(p.next == null) {p.next = prev;return p;}ListNode ph = process(p,p.next);p.next = prev;return ph;}
}

复杂度分析

  • 时间复杂度:O(n),需要遍历整个链表。
  • 空间复杂度:O(n),递归调用压栈的空间取决于原链表的长度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/134145.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3D数字孪生:从3D数据采集到3D内容分析

数字孪生(Digital Twin)是物理对象、流程或系统的虚拟复制品,用于监控、分析和优化现实世界的对应物。 这些数字孪生在制造、工程和城市规划等领域变得越来越重要,因为它们使我们能够在现实世界中实施改变之前模拟和测试不同的场景…

算法宝典2——Java版本(此系列持续更新,这篇文章目前3道)(有题目的跳转链接)(此份宝典包含了二叉树的算法题)

注:由于字数的限制,我打算把算法宝典做成一个系列,一篇文章就20题!!! 目录 一、二叉树的算法题(目前3道) 1. 平衡二叉树(力扣) 2. 对称二叉树&#xff0…

MySQL最新版8.1.0安装配置教程

目录 目录 前言 安装流程图 1,MySQL数据库是什么? 2,下载zip压缩包 3,解压到要安装的目录 4,添加环境变量 4.1,找到环境变量 4.2,进行环境变量的添加 5.新建mysql 配置文件 6、安装mysql服务 7、初始化数据文件 8、启动mysql …

Java面向对象编程

下列关于线性链表的叙述中,正确的是( ) A. 各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致 B. 各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续 C. 进行插入与删除时&#x…

gitlab操作

1. 配置ssh 点击访问 2. 创建新分支与切换新分支 git branch 新分支名 // 创建 git checkout 新分支名 // 切换到新分支3. 查看当前分支 git branch*所指的就是当前所在分支 4. 本地删除文件后与远程git同步 git add -A git commit -m "del" git push

如何根据性能需求进行场景设计?

场景设计一 探索 测试环境 客户端: win10 这里可以用linux,但没用,因为想直观查看结果。 被测环境:linux X86 4核CPU16G内存 被测接口:登录接口,没有做数据驱动。 在测试执行前,先使用influxSQL把influxdb的数据清理一下,以防影响结果查看。 有这么一个需求,要求系…

cs224w_colab3_2023 And cs224w_colab4_2023学习笔记

class GNNStack(torch.nn.Module):def __init__(self, input_dim, hidden_dim, output_dim, args, embFalse):super(GNNStack, self).__init__() #这里的继承表示参见 https://blog.csdn.net/wanzew/article/details/106993425 # 继承时运行继承类别的函数 总之 __mro__的目的…

银河麒麟操作系统安装人大金仓数据库--九五小庞

一、环境要求 硬件:内存512M以上,磁盘空间10G以上软件:主流Linux操作系统,本机使用kylin-v10安装包准备:官网下载数据库文件镜像以及授权文件 https://www.kingbase.com.cn/rjcxxz/index.htm 二、配置内核参数 vim /e…

flink-1.14.4启动报错setPreferCheckpointForRecovery(Z)v

从flink1.12升级到flink1.14,修改了pom.xml的flink-version,打包的时候发现报错: // 当有较新的 Savepoint 时,作业也会从 Checkpoint 处恢复env.getCheckpointConfig().setPreferCheckpointForRecovery(true); 于是屏蔽了这段配置…

C++中的导入include,头文件,extern,main函数入口及相关编译流程

结论: 1:#include就是复制粘贴 2:C编译的时候,在链接之前,各个文件之间实际上没有联系,只有到了链接的阶段,系统才会到各个cpp文件中去找需要的文件; 一:include的作用…

MCU软核 3. Xilinx Artix7上运行cortex-m3软核

0. 环境 - win10 vivado 2018.3 keil mdk - jlink - XC7A35TV12 1. 下载资料 https://keilpack.azureedge.net/pack/Keil.V2M-MPS2_DSx_BSP.1.1.0.pack https://gitee.com/whik/cortex_m3_on_xc7a100t 2. vivado 2018 Create Project -> Next -> -> Project n…

timer trigger function

创建(使用vscode) 选择Timer trigger 命名 设置多久触发一次(该语句是5分钟一次) 创建完成 在下面直接编辑想要运行的代码。

Redis-渐进式遍历scan的使用

目录 1、为什么使用渐进式遍历? 2、scan的使用 3、渐进式遍历的缺点 4、补充知识点:redis中也区分database 1、为什么使用渐进式遍历? 前面的博客中,我们有提到使用keys *来获取所有的key,但这种办法,…

看好多人都在劝退学计算机,可是张雪峰又 推荐过计算机,所以计算机到底是什么样 的?

张雪峰高考四百多分,但是他现在就瞧不起400多分的学生。说难听点,六七百分的 热门专业随便报谁不会啊? 计算机专业全世界都是过剩的,今年桂林电子科技,以前还是华为的校招大学,今年 计算机2/3待业。这个世…

golang iris框架 + linux后端运行

go mod init myappgo get github.com/kataras/iris/v12latestpackage mainimport "github.com/kataras/iris/v12"func main(){app : iris.New()app.Listen(":port") }打包应用 go build main.go开启服务 #nohup ./程序名称 nohup ./main关闭后台 #ps -e…

电荷型 和 IEPE/ICP型振动传感器的比较

PE(压电式)和IEPE(集成电路压电式,PCB公司叫做ICP)传感器的对比说明,供各位参考。 1. PE/IEPE传感器的敏感元件均为压电晶体,通过压电效应感受被测物理量。 2.PE传感器:输出电荷量,也叫电荷传感器。不需要供电,两根信号线,可直接接入电荷放大器进行测量。 优点―――结…

模拟实现链式二叉树及其结构学习——【数据结构】

W...Y的主页 😊 代码仓库分享 💕 之前我们实现了用顺序表完成二叉树(也就是堆),顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树,并且实现链式二叉树,这篇博客与递归息息相关&a…

Java-华为真题-预定酒店

需求: 放暑假了,小王决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为n的数组A),他的心理价位是x元,请帮他筛选出k个最接近x元的酒店(n>k>0)&#xff…

Java面向对象,全程无废话,偏实战

面向对象 定义 / 使用类 // src/Phone.java public class Phone {// 类属性String brand "苹果";int price 7999;// 类方法public void call() {System.out.println("打电话");}public void sendMessage() {System.out.println("发短信");} …

GeoJSON转STL:地形3D打印

我们通过将 GeoJSON 形状坐标提取到点云中并使用 Open3d 应用泊松重建,从 GeoJSON 数据重建 STL 网格。 推荐:用 NSDT编辑器 快速搭建可编程3D场景 我对打印 GeoJSON 山丘的第一次尝试深感不满,因此想出了一个三步流程,仅使用开源…