反转链表、链表内指定区间反转

反转链表

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。以上转换过程如下图所示:

在这里插入图片描述
示例:

输入:{1,2,3}
返回值:{3,2,1}

好久好久没有刷题了,这一年大多在写Shell脚本或者Python脚本去了,已经忘记自己是C++起家的了,好几天前大页表吴同学找了两个题目说有意思让我试一下,害,当天晚上没做出来,有时间了再看这题目,其实就是头插法,尾插法是正序,头插法就是反转了,代码附上,关键是第二题。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <cstddef>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}
};

链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。
在这里插入图片描述
这个题目首先我的想法就是把第一题反转的函数用上,然后把只需要截断反转再连接就可以了。我们使用示例{1,2,3,4,5},2,4。

第一种思路:

首先是找到需要反转的区间链表,

ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;ListNode* pre = dummyNode;
for(int i=0;i<m-1;i++){pre = pre->next;
}ListNode* rightNode = pre ;
for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;
}ListNode* leftNode = pre->next;//leftNode = {2,3,4,5}
ListNode* cur = rightNode->next;//后置链表 cur = {5}//截断链表
pre->next=NULL;//前置链表截断 pre = {1}
rightNode->next=NULL;//后置链表截断 leftNode = {2,3,4}

反转函数:

ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;
}

得到反转后的区间后,前置部分直接链接,后置部分通过遍历到反转区间链表的最后一个元素指向最后一部分。

ListNode* mid = ReverseList(leftNode);//mid = {4,3,2}pre->next = mid;
while (mid ->next)mid = mid -> next;
mid ->next = cur;
return dummyNode->next;

完整代码:

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ListNode* mid = ReverseList(leftNode);pre->next = mid;while (mid ->next)mid = mid -> next;mid ->next = cur;return dummyNode->next;}
};

第二种思路:

第二种思路就是反转函数返回一个链表有点多此一举,只需要在反转函数里对链表进行操作即可。
反转函数:

void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}
}

反转后:

//反转前 leftNode = {2,3,4} rightNode = {4}
ReverseList(leftNode);
//反转后 leftNode = {2} rightNode = {4,3,2}
pre->next = rightNode;
leftNode->next = cur;
return dummyNode->next;

完整代码:

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ReverseList(leftNode);pre->next = rightNode;leftNode->next = cur;return dummyNode->next;}
};

链表介绍

链表(Linked List)是一种线性数据结构,其中的元素(通常称为节点)按顺序排列,每个节点包含两部分信息:存储数据的部分和指向下一个节点的指针或引用。链表中的每个节点通过指针连接在一起,因此它不需要在内存中连续存储。链表有几种常见的形式:

  • 单向链表(Singly Linked List):每个节点只包含一个指向下一个节点的指针,链表是单向的,无法向后遍历。
  • 双向链表(Doubly Linked List):每个节点包含两个指针,一个指向下一个节点,另一个指向前一个节点,因此可以双向遍历。
  • 循环链表(Circular Linked List):链表的最后一个节点指向链表的第一个节点,形成一个环。

链表的优点:

  • 动态内存分配:链表不需要预先定义大小,可以根据需要动态增长或缩小。
  • 插入和删除操作:链表的插入和删除操作可以在常数时间内完成,特别是对于已知位置的节点。

链表的缺点:

  • 随机访问:由于链表的元素不在连续的内存位置,因此不能像数组一样通过索引进行随机访问,必须从头节点开始遍历。

链表广泛应用于实现队列、栈以及某些复杂数据结构,如图和哈希表的底层实现。

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

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

相关文章

关于win11电脑连接wifi的同时,开启热点供其它设备连接

背景&#xff1a; 我想要捕获手机流量&#xff0c;需要让手机连接上电脑的热点。那么问题来了&#xff0c;我是笔记本电脑&#xff0c;只能连接wifi上网&#xff0c;此时我的笔记本电脑还能开启热点供手机连接吗&#xff1f;可以。 上述内容&#xff0c;涉及到3台设备&#x…

Linux编辑器 - vim

目录 一、vim 的基本概念 1. 正常/普通/命令模式(Normal mode) 2. 插入模式(Insert mode) 3. 末行模式(last line mode) 二、vim 的基本操作 三、vim 正常模式命令集 1. 插入模式 2. 移动光标 3. 删除文字 4. 复制 5. 替换 6. 撤销上一次操作 7. 更改 8. 调至指定…

靓车汽车销售网站(源码+数据库+报告)

基于SpringBoot靓车汽车销售网站&#xff0c;系统包含两种角色&#xff1a;管理员、用户,系统分为前台和后台两大模块&#xff0c;主要功能如下。 前台功能简介&#xff1a; - 首页&#xff1a;展示网站的概要信息和推荐车辆。 - 车辆展示&#xff1a;展示可供销售的汽车。 - …

数据集-目标检测系列- 花卉 鸡蛋花 检测数据集 frangipani >> DataBall

数据集-目标检测系列- 花卉 鸡蛋花 检测数据集 frangipani >> DataBall DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 贵在坚持&#xff01; 数据样例项目地址&#xff1a; * 相关项目 1&#xff09;数据集…

数据库基础(MySQL)

1. 数据库基础 1.1 什么是数据库 存储数据用文件就可以了&#xff0c;为什么还要弄个数据库? 文件保存数据有以下几个缺点&#xff1a; 文件的安全性问题文件不利于数据查询和管理文件不利于存储海量数据文件在程序中控制不方便 数据库存储介质&#xff1a; 磁盘内存 为…

stm32cubemx+VSCODE+GCC+makefile 开发环境搭建

title: stm32cubemxVSCODEGCCmakefile 开发环境搭建 tags: FreertosHalstm32cubeMx 文章目录 内容往期内容导航第一步准备环境vscode 插件插件配置点灯 内容 往期内容导航 第一步准备环境 STM32CubeMXVSCODEMinGWOpenOcdarm-none-eabi-gcc 然后把上面下载的软件 3 4 5 bin 文…

【网络】网络抓包与协议分析

网络抓包与协议分析 一. 以太网帧格式分析 这是以太网数据帧的基本格式&#xff0c;包含目的地址(6 Byte)、源地址(6 Byte)、类型(2 Byte)、数据(46~1500 Byte)、FCS(4 Byte)。 Mac 地址类型 分为单播地址、组播地址、广播地址。 单播地址&#xff1a;是指第一个字节的最低位…

el-cascader 使用笔记

1.效果 2.官网 https://element.eleme.cn/#/zh-CN/component/cascader 3.动态加载&#xff08;官网&#xff09; <el-cascader :props"props"></el-cascader><script>let id 0;export default {data() {return {props: {lazy: true,lazyLoad (…

一分钟学习数据安全——IAM数据安全的安当实践

数字化进程推进加速&#xff0c;数据已经成为企业最重要的资产。越来越多的企业引入IAM来加强数据安全&#xff0c;确保数据在生产、存储、使用过程中的身份安全。IAM&#xff08;Identity and Access Management&#xff0c;身份与访问管理&#xff09;主要用于管理和控制用户…

使用 Axios 拦截器优化 HTTP 请求与响应的实践

目录 前言1. Axios 简介与拦截器概念1.1 Axios 的特点1.2 什么是拦截器 2. 请求拦截器的应用与实践2.1 请求拦截器的作用2.2 请求拦截器实现 3. 响应拦截器的应用与实践3.1 响应拦截器的作用3.2 响应拦截器实现 4. 综合实例&#xff1a;一个完整的 Axios 配置5. 使用拦截器的好…

c语言数据结构与算法--简单实现线性表(顺序表+链表)的插入与删除

老规矩&#xff0c;点赞评论收藏关注&#xff01;&#xff01;&#xff01; 目录 线性表 其特点是&#xff1a; 算法实现&#xff1a; 运行结果展示 链表 插入元素&#xff1a; 删除元素&#xff1a; 算法实现 运行结果 线性表是由n个数据元素组成的有限序列&#xff…

LeetCode - #139 单词拆分

文章目录 前言摘要1. 描述2. 示例3. 答案题解动态规划的思路代码实现代码解析1. **将 wordDict 转换为 Set**2. **初始化 DP 数组**3. **状态转移方程**4. **返回结果** **测试用例**示例 1:示例 2:示例 3: 时间复杂度空间复杂度总结关于我们 前言 本题由于没有合适答案为以往遗…

【第4章 | 分类与逻辑回归】(python机器学习)

一、逻辑回归 1.1逻辑回归 二项逻辑回归 • Binomial logistic regression model是一种分类模型 • 由条件概率P(Y|X)表示的分类模型 • 形式化为logistic distribution • X取实数&#xff0c;Y取值1,0 特点&#xff1a; • 事件的几率odds&#xff1a;事件发生与事件不发生…

Python毕业设计选题:基于python的豆瓣电影数据分析可视化系统-flask+spider

开发语言&#xff1a;Python框架&#xff1a;flaskPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 系统首页 个人中心 管理员登录界面 管理员功能界面 电影管理 用户管理 系统管理 摘要…

Scala之Array数组

可修改的Array import scala.collection.mutable.ArrayBuffer //Array:数组 //可修改的&#xff1a;ArrayBuffer //不可修改的&#xff1a;Array object Test1 {//可修改的&#xff1a;ArrayBufferdef main(args: Array[String]): Unit {//1.新建val arr1 ArrayBuffer(1,2,3)…

贴代码框架PasteForm特性介绍之select,selects,lselect和reload

简介 PasteForm是贴代码推出的 “新一代CRUD” &#xff0c;基于ABPvNext&#xff0c;目的是通过对Dto的特性的标注&#xff0c;从而实现管理端的统一UI&#xff0c;借助于配套的PasteBuilder代码生成器&#xff0c;你可以快速的为自己的项目构建后台管理端&#xff01;目前管…

麒麟网络负载均衡与高可用方案实践

安装 teamd 包。 yum -y install teamd Copy 一、配置TEAMING 查看两个网卡信息 ifconfig Copy 注意&#xff1a;根据实际网卡设备名称情况调整代码&#xff01;不同环境下网卡名称略有不同&#xff01; 根据查询的结果&#xff0c;两张网卡设备名称分别为 enp0s2 和 enp…

Python学习29天

二分查找 # 定义函数冒泡排序法从大到小排列 def bbble_sort(list):# i控制排序次数for i in range(len(list) - 1):# j控制每次排序比较次数for j in range(len(list) - 1 - i):if list[j] < list[j 1]:list[j], list[j 1] list[j 1], list[j] # 定义二分查找函数 def…

路由协议——iBGP与EBGP

一、适用场景 1、企业需要连接总部与分部&#xff0c;但总部与分部运行着不同的路由协议&#xff0c;总部到分部有自建的专线&#xff0c;端到端的设备支持BGP路由协议。 2、网络运营商&#xff0c;如电信、联通、移动等&#xff0c;各区域的ip路由表庞大&#xff0c;若要完成…

09.事件风暴

学习视频来源&#xff1a;DDD独家秘籍视频合集 https://space.bilibili.com/24690212/channel/collectiondetail?sid1940048&ctype0 文章目录 概念组成部分具体场景事件风暴寻找聚合 改进具体流程 参考 概念 事件风暴是Alberto Brandolini 发明的一种头脑风暴方法&#x…