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

【链表OJ题(四)】反转链表

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(四)
    • 1. 反转链表
      • 思路一 迭代法
        • 一、一般情况
          • 二、极端情况
            • 1.传入的链表为空时
            • 2.反转第一个结点指针的指向时
            • 3.反转最后一个结点指针的指向时
      • 思路二 头插法
  • 2.总结:

上一篇链表OJ题链接:【链表OJ题(三)】链表中倒数第k个结点

链表OJ题(四)

1. 反转链表

链接:206. 反转链表
描述:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
在这里插入图片描述

示例1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例2:
输入:head = [1,2]
输出:[2,1]
示例3:
输入:head = []
输出:[]

思路一 迭代法

反转一个单向链表,可以看成是将链表中的每个结点的指向反向(即从后一个结点指向前一个结点),我们在考虑情况的时候,还是可以先考虑一般情况,再考虑极端情况。

一、一般情况

要使两个结点之间的指针指向反转,看似用两个变量足矣,直接让后一个结点指向前一个结点。但是仔细思考后发现并没有那么简单,我们如果直接让后一个结点指向前一个结点,那么后一个结点所指向的再后面一个结点的位置就无从知晓了。所以,我们还得定义3个指针变量:n1,n2,n3

n1:记录指针指向将要反转的结点反转后要指向的位置。
n2:记录指针指向将要反转的结点。
n3:记录指针指向将要反转的结点的下一个结点。
在这里插入图片描述
在反转时,首先让n2指向的结点指向n1指向的位置,
在这里插入图片描述

然后让n1,n2,n3指针统一后移,准备执行下一对结点之间指向的反转。
如此进行下去,所有的结点指向都将反转。

二、极端情况

极端情况,也就是反转第一个结点指针的指向和反转最后一个结点指针的指向,以及传入的链表为空时的情况。

1.传入的链表为空时

我们可以发现,若传入的链表为空,那么我们根本就不需要对链表进行任何操作,直接返回传入的头指针即可。如果再稍加思考,当传入链表只有一个结点时,我们也不需要对链表进行任何操作,直接返回传入的头指针也没问题。

2.反转第一个结点指针的指向时

因为n2记录的是指针指向将要反转的结点,所以当反转第一个结点指针的指向时,n2指针便指向的是第一个结点。
在这里插入图片描述

因为在我们反转过程中就是让n2指向的结点指向n1指向的位置,所以我们只需将n1的初始值赋值为NULL即可。这样,反转后就让第一个结点指针指向NULL了(即反转后的最后一个结点指向空)。

3.反转最后一个结点指针的指向时

当最后一个结点的指针指向被反转时,n2刚好指向最后一个结点,
在这里插入图片描述

在指针反转完成后,n1,n2,n3指针统一向后移动,位置如下:
在这里插入图片描述

我们可以发现逻辑上是没有问题的,而且此时也发现了遍历链表时的终止条件和需要返回的新的头指针,即当n2指针为NULL时停止遍历,并且返回n1指针指向的位置。
注意 这时这3个指针统一后移时,n3指针的后移将失败,因为n3后移前指向的是NULL,我们不能执行以下这句代码:

n3 = n3->next;

所以我们后移n3指针前需判断其是否为空。

代码实现

struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL || head->next == NULL)//当链表为空或只有一个结点时,无需操作return head;//直接返回struct ListNode* n1 = NULL;//记录指针指向将要反转的结点反转后要指向的位置。struct ListNode* n2 = head;//记录指针指向将要反转的结点。struct ListNode* n3 = head->next;//记录指针指向将要反转的结点的下一个结点。while (n2)//n2为NULL时,停止遍历{n2->next = n1;//反转结点指向n1 = n2;//指针后移n2 = n3;//指针后移if (n3)//判断n3是否为NULLn3 = n3->next;//指针后移}return n1;//返回n1指针指向的位置
}

在这里插入图片描述

思路二 头插法

如果觉得上面这种思路有点绕的话,可以看看下面这种思路:将原链表的结点,从头到尾一个个地拿下来头插到一个新链表中,这个新链表起始时为一个空链表。
在这里插入图片描述

这样依次进行下去,最终就能得到一个“反转后的链表”。

代码实现

struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;//记录当前待头插的结点struct ListNode* newhead = NULL;//新链表初始时为空while (cur)//链表中结点头插完毕时停止循环{struct ListNode* next = cur->next;//记录下一个待头插的结点cur->next = newhead;//将结点头插至新链表newhead = cur;//新链表头指针后移cur = next;//指向下一个待头插的结点}return newhead;//返回反转后的头指针
}

在这里插入图片描述

2.总结:

今天我们通过两种思路分析并完成反转链表这道链表OJ题目,也更加深层次了解和使用了头插法这个思路,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

相关文章:

【链表OJ题(四)】反转链表

​ ​📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(四)1. 反转…...

java ArrayList源码分析(深度讲解)

ArrayList类的底层实现ArrayList类的断点调试空参构造的分步骤演示(重要)带参构造的分步骤演示一、前言大家好,本篇博文是对单列集合List的实现类ArrayList的内容补充。之前在List集合的万字详解篇,我们只是拿ArrayList演示了List…...

【网络编程】零基础到精通——NIO基础三大组件和ByteBuffer

一. NIO 基础 non-blocking io 非阻塞 IO 1. 三大组件 1.1 Channel & Buffer channel 有一点类似于 stream,它就是读写数据的双向通道,可以从 channel 将数据读入 buffer,也可以将 buffer 的数据写入 channel,而之前的 st…...

操作系统 - 1. 绪论

目录操作系统基本概念概念特征功能操作系统的分类与发展手工操作单道批处理系统多道批处理系统分时系统实时系统操作系统的运行环境CPU 运行模式中断和异常的处理系统调用程序的链接与装入程序运行时内存映像和地址空间操作系统的体系结构操作系统的引导操作系统基本概念 概念…...

详谈parameterType与resultType的用法

resultMap 表示查询结果集与java对象之间的一种关系,处理查询结果集,映射到java对象。 resultMap 是一种“查询结果集---Bean对象”属性名称映射关系,使用resultMap关系可将将查询结果集中的列一一映射到bean对象的各个属性&#…...

【Linux】进程概念、fork() 函数 (干货满满)

文章目录📕 前言📕 进程概念📕 Linux下查看进程的两种方法方法一方法二📕 pid() 、ppid() 函数📕 fork() 函数、父子进程初识再理解📕 fork做了什么📕 如何理解 fork 有两个返回值📕…...

【动态规划】最长上升子序列、最大子数组和题解及代码实现

Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...

Ajax进阶篇02---跨域与JSONP

前言❤️ 不管前方的路多么崎岖不平,只要走的方向正确,都比站在原地更接近幸福 ❤️Ajax进阶篇02---跨域与JSONP一、Ajax进阶篇02---跨域与JSONP(1)同源策略1.1 什么是同源1.2 什么是同源策略(2)跨域2.1 什…...

C 语言编程 — 线程池设计与实现

目录 文章目录目录线程池(Thread Pool)tiny-threadpool数据结构设计Task / JobTask / Job QueueWorker / ThreadThread Pool ManagerPublic APIsPrivate Functions运行示例线程池(Thread Pool) 线程池(Thread Pool&am…...

并发编程要点

Java并发编程中的三大特性分别是原子性、可见性和有序性,它们分别靠以下机制实现: 原子性:原子性指的是对于一个操作,要么全部执行,要么全部不执行。Java提供了一些原子性操作,例如AtomicInteger等&#xf…...

HDFS黑名单退役服务器

黑名单:表示在黑名单的主机IP地址不可以,用来存储数据。 企业中:配置黑名单,用来退役服务器。 黑名单配置步骤如下: 1)编辑/opt/module/hadoop-3.1.3/etc/hadoop目录下的blacklist文件 添加如下主机名称&…...

基于stm32智能语音电梯消毒系统

这次来分享个最近做的项目,stm32智能语音电梯消毒系统功能说明:在电梯,房间,客道区域内,检测到人,则执行相关动作!例如继电器开关灯,喷洒酒精等行为。手机app/微信小程序可以控制需要…...

FreeRTOS系列第1篇---为什么选择FreeRTOS?

1.为什么学习RTOS? 作为基于ARM7、Cortex-M3硬件开发的嵌入式工程师,我一直反对使用RTOS。不仅因为不恰当的使用RTOS会给项目带来额外的稳定性风险,更重要的是我认为绝大多数基于ARM7、Cortex-M3硬件的项目,还没复杂到使用RTOS的地…...

基于.NET Core内置浏览器窗体应用程序界面框架

更多开源项目请查看:一个专注推荐.Net开源项目的榜单 平常我们在做项目过程中,桌面软件具备操作高效、利用本地计算机做一些复杂运算、或者设定快捷操作等优势,但是桌面软件也有很多缺点,比如升级问题、系统兼容问题、系统bug排查…...

【数据结构初阶】一文带你学会归并排序(递归非递归)

目录 前言 递归实现 代码实现 非递归实现 代码实现 总结 前言 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 作为一种典型的分而治之思想…...

Simulink壁咚(一)——What and How

目录 一、前言 二、Simulink 知多少 三、滤波算法 四、Model Verification 五、Model Coverage 六、Simulink测试实例 七、Simulink Test 八、Test Manager 九、Test Harness 十、 学习 一、前言 Simulink从2017b以后更加工程化和实用化,基于MBD的功能日趋…...

【PyTorch】Pytorch基础第0章

本文参加新星计划人工智能(Pytorch)赛道:https://bbs.csdn.net/topics/613989052 这是目录PyTorch的简介PyTorch 构建深度学习模型的步骤搭建pytorch使用环境PyTorch的简介 PyTorch 是一个开源的机器学习框架,由 Facebook 的人工智能研究院(…...

Android学习总结

积累熟练掌握 Java 语言,面向对象分析设计能力,反射原理,自定义注解及泛型,多次采用设计模式重构公司项目;熟练掌握 IVM 原理,反射,动态代理以及对 ClassLoader 热修复有比较深的理解&#xff1…...

虚拟机ubuntu安装samba服务

安装samba apt-get install samba 新建一个共享目录 mkdir /home/l/work chmod 777 /home/l/work 配置服务 配置 /etc/samba/smb.confsudo smbpasswd -a l(添加用户名名称) 防火墙关闭 Ubuntu中 我们使用命令查看当前防火墙状态; sudo ufw status inactive状态是防火墙关闭…...

开发板中的内存压力测试,你了解多少?

1. 测试目的内存压力测试的目的是评估开发板中的内存子系统性能和稳定性,以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景,这些场景对内存的要求通常比较高。其内存压力测试的主要目的有:1.对确…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

pam_env.so模块配置解析

在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...

CSS | transition 和 transform的用处和区别

省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...