「题解」反转链表 返回中间节点

文章目录

  • 🍉题目1:反转链表
  • 🍉解析
    • 🍌解法一:创建一个新链表
    • 🍌解法二:直接操作原链表
  • 🍉题目2:返回中间节点
    • 🍌解法一:快慢指针
    • 🍌解法二:两次遍历

🍉题目1:反转链表

在这里插入图片描述
在这里插入图片描述

🍉解析

🍌解法一:创建一个新链表

这种解法算是比较通用的,就题目如果要求要对某个对象进行操作,那我们一般可以考虑创建一个新的对象,按照题目要求把符合条件的元素放进去。
现在要反转的话,那就相当于先遍历原链表,每遇到一个节点就头插插入新链表(越后面的节点插入后就到新链表越靠前的位置,这应该很好理解)

如何创建新链表?首先得先定义一个指针:newhead,newhead 是新链表的头节点。第一次插入得考虑新链表为空的情况
代码如下:

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){ struct ListNode* next = cur->next;  //头插前先用next保存cur下次要指向的节点//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}

🍌解法二:直接操作原链表

设置三个变量n1、n2 和 n3,每次将 n2 所指的节点的 next 指向 n1 ,然后 n1 和 n2 和 n3 继续往前走,直到 n3 为空(即下图第四个节点的next)。
这个思路简而言之就是:把一个节点的next改为指向前一个节点。

在这里插入图片描述
在这里插入图片描述在这里插入图片描述
在这里插入图片描述

为啥要弄一个n3呢?因为 n2 不仅要让它的 next 指向 n1,同时你还要让 n2 往后走,而往后走也要用到next,这两个都会改变 n2 或者 n2->next ,所以就用一个 n3 保存 n2 的next。

下面是代码:

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(!head){return NULL;}ListNode* n1 = NULL;ListNode* n2 = head;ListNode* n3 = head->next;while(n2) {n2->next = n1;n1 = n2;n2 = n3;if(n3) {n3 = n3->next;}}return n1;
}

注意:n3 在往前推进的时候要先判断是否为空,因为它为空的话就没法解引用,也就没有next了(这个点在前面单链表那篇文章中见到不少次了)


🍉题目2:返回中间节点

在这里插入图片描述

🍌解法一:快慢指针

顾名思义,就是弄两个指针,分别记为 fast 和 slow,其中快指针一次走两个单位;慢指针一次走一个。这样,当快指针遍历完链表时,慢指针刚好到中间的节点。若为偶数个节点,题目说返回第二个中间节点,你去画图会发现按这种解法,slow刚好走到第二个。
这种方法的原理也很简单,就是数学上的“路程差”。

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head,*fast = head;while(fast && fast->next) {fast = fast->next->next;slow = slow->next;}return slow;
}

快指针和慢指针的速度你可以根据需求自定义,而非说快指针的速度一定是慢指针的两倍。这种思想除了用于解决中间节点问题,还可以解决找倒数第 n 个节点的问题。

比如我们要找某链表倒数第三个节点,那就可以让快指针先走三步,此后快慢指针每次都走一步,快指针走完时(终止条件是快指针为空)

🍌解法二:两次遍历

先定义一个计数器count,然后第一次遍历每过一个节点count就+1,然后第二次使用for循环遍历count / 2次,循环具体要走多少次,你举个特例就可以推出来了(比如3个节点,4个节点)

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pcur = head;int count = 1;while(pcur->next) {pcur = pcur->next;count++;}pcur = head;for(int i = 0;i<count/2;i++){pcur = pcur->next;}return pcur;
}

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

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

相关文章

工作量证明是解决拜占庭将军问题的唯一办法

号外&#xff1a;教链内参11.10《以太坊反攻》 文 | Oleg Andreev. 2014.5.23. 原标题&#xff1a;Proof That Proof-of-Work is the Only Solution to the Byzantine Generals Problem &#xff08;本文是&#xff09;回复Vlad_Roberto的话&#xff1a;“不&#xff0c;&#…

视频剪辑助手:轻松实现视频随机分割并提取音频保存

随着社交媒体和视频平台的日益普及&#xff0c;视频制作和分享已成为人们日常生活的一部分。无论是分享个人生活&#xff0c;还是展示才艺&#xff0c;或是推广产品&#xff0c;视频都是一个非常有效的工具。但是&#xff0c;视频制作往往涉及到大量的视频剪辑工作&#xff0c;…

算法导论6:摊还分析,显式与隐式

P258 摊还分析概念 聚合分析&#xff0c;利用它&#xff0c;我们证明对于n&#xff0c;一个n个操作的序列最坏情况下的花费的总时间为T(n)&#xff0c;因此&#xff0c;在最坏情况下&#xff0c;每个操作的平均代价&#xff08;摊还代价&#xff09;为T(n)/n 举了例子来形容这…

模板初阶 C++

目录 泛型编程 函数模板 概念 格式 原理 函数模板的实例化 类模板 格式 类模板的实例化 泛型编程 当我们要实现一个交换函数&#xff0c;我们可以利用函数重载实现&#xff0c;但是有几个不好的地方 1.函数重载仅仅是类型不同&#xff0c;代码复用率较低&#xff0c;只…

FlinkSQL聚合函数(Aggregate Function)详解

使用场景&#xff1a; 聚合函数即 UDAF&#xff0c;常⽤于进多条数据&#xff0c;出⼀条数据的场景。 上图展示了⼀个 聚合函数的例⼦ 以及 聚合函数包含的重要⽅法。 案例场景&#xff1a; 关于饮料的表&#xff0c;有三个字段&#xff0c;分别是 id、name、price&#xff0…

visual studio 启用DPI识别功能

在开发widow程序时&#xff0c;有时必须将电脑 设置-->显示-->缩放与布局-->更改文本、应用项目的大小-->100%后&#xff0c;程序的画面才能正确运行&#xff0c;居说这是锁定了dpi的原因&#xff0c;需要启dpi识别功能。设置方法如下&#xff1a; 或者

Python开源项目PGDiff——人脸重建(Face Restoration),模糊清晰、划痕修复及黑白上色的实践

python ansconda 等的下载、安装等请参阅&#xff1a; Python开源项目CodeFormer——人脸重建&#xff08;Face Restoration&#xff09;&#xff0c;模糊清晰、划痕修复及黑白上色的实践https://blog.csdn.net/beijinghorn/article/details/134334021 友情提示&#xff1a; …

Vue23组件自定义事件 和 解绑事件

Vue2&3组件自定义事件 和 解绑事件 Vue2组件自定义事件 功能&#xff1a;父组件绑定数据&#xff0c;子组件触发事件。&#xff08;父绑子触发&#xff09; 实现步骤&#xff08;前三步在父组件实现&#xff0c;第四步在子组件实现&#xff09;&#xff1a; 第一步&#…

ArcGIS进阶:栅格计算器里的Con函数使用方法

本实验操作为水土保持功能重要性评价&#xff1a; 所用到的数据包括&#xff1a;土地利用类型数据&#xff08;矢量&#xff09;、植被覆盖度数据&#xff08;矢量&#xff09;和地形坡度数据&#xff08;栅格&#xff09;。 由于实验数据较少&#xff0c;其思路也较为简单&a…

立体相机标定

相机成像过程中涉及的4个坐标系&#xff1a; 1、世界坐标系&#xff1a;由用户定义的三维世界坐标系&#xff0c;描述物体和相机在真实世界中的位置&#xff0c;原点可以任意选择。 2、相机坐标系&#xff1a;以相机的光心为坐标原点&#xff0c;X轴和Y轴平行于图像坐标系的X轴…

OpenHarmony 社区运营报告(2023 年 10 月)

● 截至 2023 年 10 月&#xff0c;OpenHarmony 社区共有 51 家共建单位&#xff0c;累计超过 6200 名贡献者产生 24.2 万多个 PR&#xff0c;2.3 万多个 Star&#xff0c;6.1 万多个 Fork&#xff0c;59 个 SIG。 ● OpenHarmony 4.0 版本如期而至&#xff0c;开发套件同步升级…

【js逆向实战】某sakura动漫视频逆向

写在前面 再写一个逆向实战&#xff0c;后面写点爬虫程序来实现一下。 网站简介与逆向目标 经典的一个视频网站&#xff0c;大多数视频网站走的是M3U8协议&#xff0c;就是一个分段传输&#xff0c;其实这里就有两个分支。 通过传统的m3u8协议&#xff0c;我们可以直接进行分…

建行广东省江门市分行走进农村地区开展反假货币宣传

人民对美好生活的向往&#xff0c;涉及方方面面&#xff0c;小至“钱袋子”安全。建行广东省江门市分行落实当地监管部门部署&#xff0c;积极扛起维护国家金融安全的重要政治责任&#xff0c;深入农村地区开展反假货币宣传工作&#xff0c;助力构建农村反假货币工作长效机制。…

拓扑排序软件设计——ToplogicalSort_app(含有源码、需求分析、可行性分析、概要设计、用户使用手册)

拓扑排序软件设计 前言1. 需求分析2. 可行性分析2.1 简介2.2 技术可行性分析2.2.1 技术实现方案2.2.2 开发人员技能要求2.2.3 可行性 2.3 操作可行性分析2.4 结论 3. 项目报告3.1 修订历史记录3.2 软硬件环境3.3 需求分析3.4 详细设计3.4.1 类设计3.4.2 核心流程描述3.4.3 核心…

安全通信网络(设备和技术注解)

网络安全等级保护相关标准参考《GB/T 22239-2019 网络安全等级保护基本要求》和《GB/T 28448-2019 网络安全等级保护测评要求》 密码应用安全性相关标准参考《GB/T 39786-2021 信息系统密码应用基本要求》和《GM/T 0115-2021 信息系统密码应用测评要求》 1网络架构 1.1保证网络…

Zephyr-7B论文解析及全量训练、Lora训练

文章目录 一、Zephyr&#xff1a;Direct Distillation of LM Alignment1.1 开发经过1.1.1 Zephyr-7B-alpha1.1.2 Zephyr-7B-beta 1.2 摘要1.3 相关工作1.4 算法1.4.1 蒸馏监督微调&#xff08;dSFT&#xff09;1.4.2 基于偏好的AI反馈 (AIF&#xff09;1.4.3 直接蒸馏偏好优化&…

论文阅读[121]使用CAE+XGBoost从荧光光谱中检测和识别饮用水中的有机污染物

【论文基本信息】 标题&#xff1a;Detection and Identification of Organic Pollutants in Drinking Water from Fluorescence Spectra Based on Deep Learning Using Convolutional Autoencoder 标题译名&#xff1a;基于使用卷积自动编码器的深度学习&#xff0c;从荧光光谱…

Clickhouse学习笔记(8)—— 建表优化

数据类型 时间字段 建表时能用数值型或日期时间类型&#xff08;DateTime&#xff09;表示的字段就不要用字符串 因为clickhouse进行分区时一般使用时间字段来进行分区&#xff0c;而将时间字段使用DateTime表示&#xff0c;不需要经过函数转换处理&#xff0c;执行效率高、…

黑窗口连接远程服务

ssh root192.168.x.x 回车输入密码 查看docker docker ps 停止正在运行的服务 docker stop xxxxx 删除服务 docker rm xxxxx 查看镜像 docker images 删除镜像 docker rmi xxxxx 删除镜像 启动并运行整个服务 docker compose up -d jar包名称 idea 使用tcp方式连接docker 配置d…

深度探究深度学习常见数据类型INT8 FP32 FP16的区别即优缺点

定点和浮点都是数值的表示&#xff08;representation&#xff09;&#xff0c;它们区别在于&#xff0c;将整数&#xff08;integer&#xff09;部分和小数&#xff08;fractional&#xff09;部分分开的点&#xff0c;点在哪里。定点保留特定位数整数和小数&#xff0c;而浮点…