单链表OJ题(2):反转链表(三指针法)、找中间节点(快慢指针)
目录
1.反转链表
反转链表总结:
2.链表的中间节点(快慢指针法)
快慢指针法总结
1.反转链表

在这道题中,我们需要把一个单链表反转它们的指向,这里,我们给出了一个好理解的简单解法,就是用三个指针去解决这道题。 先给出完整的代码。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//创建头指针ListNode* n1 = NULL;ListNode* n2 = head;if(n2==NULL){return NULL;}ListNode* n3 = n2->next;while(n2){n2->next=n1;n1 = n2;n2 = n3;if(n3)n3=n3->next;}return n1;
}
假设,我们的原链表为head,我们申请了n1,n2,n3三个指针,其中,n1初始化为NULL,n2初始化为head(图中的第一个节点),n3初始化为head->next(也就是图中的第二个节点)

第一次操作:

第二次操作:

第三次操作:

第四次操作:(注意:最后一次操作,n3的指针指向,不能让n3出现NULL->NULL的情况)

然后,我们的步骤如下:
1、遍历原链表中的每个节点,每次遍历,先使n1的指针指向n2的节点(n1=n2),然后让n2的节点指向n3(n2=n3),最后让n3的节点指向n3的下一个节点(n3=n3->next)
2、注意,要在循环中判断以下n3的指针指向,防止出现NULL->NULL的情况。
反转链表总结:
这里面最重要的是我们要改变当前的节点的指向关系的时候,注意要先把当前节点指向的下一个节点的指针保存下来。如果我们不保存就改变指向关系的化,就会导致一个严重的错误,我们原链表中当前节点的下一个节点就找不到了。如下图,当我们遍历原链表的时候,我们需要让第一个链表的节点指向NULL,但是我们没有存储第二个节点的地址,当我们改变了指向让第一个节点的地址为NULL的时候,原链表后面的节点就没办法找到。

这个时候,我们就需要在改变当前节点指向关系前将这个节点的next域存储起来,这样我们就可以实现通过n3找到原链表节点,通过n2就可以改变当前链表的指向关系。

2.链表的中间节点(快慢指针法)

(1)在看到这个题的时候,我们能够都想到的同用解法是用计数器来做 ,下面是具体步骤:
1、首先我们遍历原链表,定义一个变量count存储节点的个数,然后将每个节点都做+1的操作,这样我们就得到了链表的节点总个数count。
2、然后,我们对count/2得到中间节点的位置,然后再次遍历原链表,找到下标为:count/2的位置上的节点,并返回。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pcur = head;int count = 0;while(pcur){count++;pcur = pcur->next;}pcur = head;count /= 2;while(count--){pcur = pcur->next;}return pcur;
}
(2)这里提供一种很巧妙的解题方法,我们只需要遍历一遍链表就能够得到链表中间的位置,这个就是我们接下来介绍的快慢指针法了。
先给出代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(head==NULL){return NULL;}//定义快慢指针ListNode* slow ,*fast; slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
1、刚开始,我们创建两个指针,slow和fast都指向头节点.
2、接下来,我们规定,slow每次走一个节点,fast每次走两个节点,当遍历结束时,slow指针指向的节点就是我们需要的中间节点。
3、循环结束的条件,fast!==NULL && fast->next!=NULL。
我们继续深入解析以下结束的循环条件是如何得到的,这就得要根据节点个数是否为奇数和偶数来确定。
1)当讨论的节点个数为偶数的时候:
阶段1:

阶段2:

阶段3:
从这里可以得到,当我们得fast指针指向NULL时,循环结束,此时,slow指向得节点正好是我们需要得中间节点。
2)当讨论的节点个数为奇数的时候:
阶段1:

阶段2:

阶段3:

从这里,我们可以看出来,当fast的next指向为NULL时,我们的循环结束,此时,slow指针指向的节点就是我们的中间节点。
然后,我们得出结论,当fast和fast->next有一个为NULL时,我们的循环条件就结束,此时我们的slow指针指向的节点就是中间节点。 (这里的)
快慢指针法总结:
这里的快慢指针法可以很快的找到我们所需要的单链表中的中间节点,代码量也很少,是一个很不错的解题思路,在涉及到用中间节点解题的时候,可以参考以下这个方法。
相关文章:
单链表OJ题(2):反转链表(三指针法)、找中间节点(快慢指针)
目录 1.反转链表 反转链表总结: 2.链表的中间节点(快慢指针法) 快慢指针法总结 1.反转链表 在这道题中,我们需要把一个单链表反转它们的指向,这里,我们给出了一个好理解的简单解法,就是用三…...
Rows 行
Goto Data Grid 数据网格 Rows 行...
十个常见的软件测试面试题,拿走不谢
所有面试问题一般建议先总后分的方式来回答,这样可以让面试官感觉逻辑性很强。 1. 自我介绍 之所以让我们自我介绍,其实是面试官想找一些时间来看简历,所以自我介绍不用太长的时间,1-2分 钟即可。 自我介绍一般按以下方式进行介…...
windows 11 配置 kafka 使用SASL SCRAM-SHA-256 认证
1. 下载安装apache-zookeeper-3.9.2 配置 \conf\zoo.cfg # The number of milliseconds of each tick tickTime2000 # The number of ticks that the initial # synchronization phase can take initLimit10 # The number of ticks that can pass between # sending a requ…...
Elasticsearch —— ES 环境搭建、概念、基本操作、文档操作、SpringBoot继承ES
文章中会用到的文件,如果官网下不了可以在这下 链接: https://pan.baidu.com/s/1SeRdqLo0E0CmaVJdoZs_nQ?pwdxr76 提取码: xr76 一、 ES 环境搭建 注:环境搭建过程中的命令窗口不能关闭,关闭了服务就会关闭(除了修改设置后重启的…...
ElSelect 组件的 onChange 和 onInput 事件的区别
偶然遇到一个问题,在 ElSelect 组件中设置 filterable 属性后,监测不到复制粘贴的内容,也就意味着不能调用接口,下拉框内容为空。 简要代码如下: <ElSelectstyle"width: 256px"multiplev-model{siteIdL…...
加密与数据提取:保护隐私的新途径
加密与数据提取:保护隐私的新途径 在数字化时代,数据已成为驱动社会进步和经济发展的关键要素。然而,随着数据量的爆炸性增长,个人隐私保护成为了一个亟待解决的问题。如何在利用数据价值的同时,确保个人隐私不被侵犯…...
博客摘录「 宋宝华:Linux文件读写(BIO)波澜壮阔的一生」2024年11月1日
同时内核会给第2页标识一个PageReadahead标记,意思就是如果app接着读第2页,就可以预判app在做顺序读,这样我们在app读第2页的时候,内核可以进一步异步预读。 每个bio对应的硬盘里面一块连续的位置,每一块硬盘里面连续…...
使用华为云数字人可以做什么
在数字化和智能化快速发展的今天,企业面临着如何提升客户体验、优化运营效率的挑战。华为云数字人作为一种创新的智能交互解决方案,为企业提供了全新的可能性,助力企业在各个领域实现智能化升级。 提升客户服务体验 华为云数字人能够模拟真…...
leetcode刷题记录——(十六)349. 两个数组的交集
(一)问题描述 . - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/intersection-of-two-arrays/ …...
vue3实现规则编辑器
组件用于创建和编辑复杂的条件规则,支持添加、删除条件和子条件,以及选择不同的条件类型。 可实现json数据和页面显示的转换。 代码实现 : index.vue: <template><div class"allany-container"><div class"co…...
【快速上手】pyspark 集群环境下的搭建(Standalone模式)
目录 前言 : 一、spark运行的五种模式 二、 安装步骤 安装前准备 1.第一步:安装python 2.第二步:在bigdata01上安装spark 3.第三步:同步bigdata01中的spark到bigdata02和03上 三、集群启动/关闭 四、打开监控界面验证 前…...
中文NLP地址要素解析【阿里云:天池比赛】
比赛地址:中文NLP地址要素解析 https://tianchi.aliyun.com/notebook/467867?spma2c22.12281976.0.0.654b265fTnW3lu长期赛: 分数:87.7271 排名:长期赛:56(本次)/6990(团体或个人)方案…...
使用AddressSanitizer内存检测
修改cmakelist.txt,在project(xxxx)后面追加: option(MEM_CHECK "memory check with AddressSanitizer" OFF) if(MEM_CHECK)set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -fsanitizeaddress")set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS…...
11月1日星期五今日早报简报微语报早读
11月1日星期五,农历十月初一,早报#微语早读。 1、六大行今日起实施存量房贷利率新机制。 2、谷歌被俄罗斯罚款35位数,罚款远超全球GDP。 3、山西吕梁:女性35岁前登记结婚,给予1500元奖励。 4、我国人均每日上网时间…...
实用篇:Postman历史版本下载
postman历史版本下载步骤 1.官方历史版本发布信息 2.点进去1中的链接,往下滑动;选择你想要的版本 例如下载v11.18版本 3.根据操作系统选择 mac:mac系统postman下载 window:window系统postman下载 4.在old version里找到对应版本下载即可 先点击download 再点击free downlo…...
微服务实战系列之玩转Docker(十七)
导览 前言Q:如何实现etcd数据的可视化管理一、创建etcd集群1. 节点定义2. 集群成员2.1 docker ps2.2 docker exec2.3 etcdctl member list 二、发布数据1. 添加数据2. 数据共享 三、可视化管理1. ETCD Keeper入门1.1 简介1.2 安装1.2.1 定义compose.yml1.2.2 启动ke…...
操作系统-实验报告单(1)
目录 1 实验目标 2 实验工具 3 实验内容、实验步骤及实验结果 一、安装虚拟机及Ubuntu 5、*存在虚拟机不能安装的问题 二、Ubuntu基本操作 1、桌面操作 2、终端命令行操作 三、在Ubuntu下运行C程序 3、*Ubuntu中编写一个Hello.c的主要程序 4 实验总结 实 验 报 告…...
rom定制系列------小米8青春版定制安卓14批量线刷固件 原生系统
💝💝💝小米8青春版。机型代码platina。官方最终版为 12.5.1安卓10的版本。客户需要安卓14的固件以便使用他们的软件。根据测试,原生pixeExpe固件适配兼容性较好。为方便客户批量进行刷写。修改固件为可fast批量刷写。整合底层分区…...
CATIA许可证常见问题解答
在使用CATIA软件的过程中,许可证问题常常是用户关心的焦点。为了帮助大家更好地理解和解决这些问题,我们整理了一份CATIA许可证常见问题解答,希望能为您提供便捷的参考。 问题一:如何激活CATIA许可证? 解答:…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
