【数据结构】【线性表】【练习】反转链表

申明

        该题源自力扣题库19,文章内容(代码,图表等)均原创,侵删!

题目

        给你单链表的头指针head以及两个整数left和right,其中left<=right,请你反转从位置left到right的链表节点,返回反转后的链表结果!

示例:

输入:[1,2,3,4,5],left=2,right=4

输出:[1,4,3,2,5]

链表结构体

struct ListNode {int val;struct ListNode *next;
};

        题目相关信息到此为止,我们一切来分析一下题目:

  1. 首先确认链表类型:无头结点的单链表
  2. 题目目的:反转链表中的某一段链表,反转就是将从头到尾数变成从尾到头数
  3. 链表可以分为两个部分,反转部分和保持部分

        如果我们把链表想象成链条,要我们把链条某一部分反过来我们会怎么做?我相信大部分人都是先将要反转的这一部分从整个链条中拆下来,然后反过来,最后接回去即可。类似的这个题目也可以用这种方法去做。

解题思路
  1. 找到需要反转部分的链表,并记录链表左侧和右侧
  2. 将该部分链表进行反转
  3. 将反转好的链表接回去
思路图解

        1.找出需要反转部分的链表,断开链表

        2.反转链表

        3.接回反转的链表

        这里有一个很重要的就是链表的反转,如图所示反转链表只需要改变指针方向即可实现,但因为单链表的不可逆性会造成很大麻烦。

        例如这里我需要将2->3改为2->NULL,假定当前遍历指针p指向2

 

        如果我直接写下p->next=NULL:

        观察链表发现链表已经断开,无法继续遍历链表。有聪明的同学已经想到,那么我加一个指针cur,在p改变next之前,cur先行一步,到达下一个结点,等p改完next再跟上cur不就可以了?

        确实也是如此,我们按这种思路继续往下走, 

先行一步:

 改变p的next

 令p=cur跟上

        然后重复操作;但仔细观察会发现, p此时要再更改next已经找不到前驱结点了,第一个结点没前驱结点所以可以直接令p->next=NULL,但第二个结点开始就不可以了。

        那么有小伙伴可能也想到了,那我加一个指针pre跟在p后面,一直指向p的前驱结点不将可以了嘛,每次改为p和next,p离开之前pre跟上p,使得p在改next时均指向p的前驱结点:

 cur先行一步

 p修改next:p->next=pre

 pre跟上p

p跟上cur 

 cur先行一步

修改p的next:p->next=pre

        到此链表反转已经完成,rehead从原来指向第一个结点变为指向最后一个结点 

        这里还有一个需要注意的点是链表的断开与重连,这里思考一下,重连需要几个结点指针?

我们看一下:

原来的1和2断开,3和4断开,反转完成之后1和3相连,2和4相连。因此我们要记录4个结点。 

代码解析

/*链表反转代码*/
void reverseLinkedList(struct ListNode* head) {struct ListNode* pre = NULL;//前驱指针--修改指针的next指向的结点struct ListNode* cur = head;//修改指针--指向要被修改next的结点struct ListNode* p = NULL;//遍历指针--遍历整个链表while (cur != NULL) {//要被修改的结点存在p= cur->next;//遍历指针向下走一位,为下一个结点反转做准备cur->next = pre;//将该结点的next指向其前驱结点pre = cur;//前驱指针跟上修改指针cur = p;//修改指针跟上遍历指针}
}struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {/*为了方便操作,我们创建一个虚拟头结点*/struct ListNode dummy;dummy.next = head;struct ListNode* prev = &dummy; // prev表示当前结点struct ListNode* rehead = NULL;//需要反转的链表第一个结点struct ListNode* pre = NULL;//需要反转部分链表的前驱结点struct ListNode* curr = NULL;//需要反转部分链表的后继结点/*遍历链表,将需要反转部分的链表从原链表中剪出来,并记录left-1和right+1两个结点*/int length = 0;while (prev->next != NULL && length < right) {//下一结点不为空且链表当前位序小于right++length;//链表当前位序+1if (length == left) {//链表当前位序=leftpre = prev;//记录第left-1位结点rehead = prev->next;//初始化新链表第一个结点,prev指向left}prev = prev->next;//当前结点向下移动一位}/*循环结束prev指向right*/pre->next = NULL;//断开链表左侧curr = prev->next;//记录right+1个结点prev->next = NULL;//断开链表右侧reverseLinkedList(rehead);//反转新链表pre->next = prev;//新链表左侧接回rehead->next = curr;//新链表右侧接回return dummy.next;
}

       

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

鸿蒙原生应用开发元服务 元服务是什么?和App的关系?(保姆级步骤)

元服务是什么&#xff1f;和App的关系&#xff1f; 元服务是是一种HarmonyOS轻量应用形态&#xff0c;用户无需安装即可使用&#xff0c;具备随处可及、服务直达、自由流转的特征。 元服务是可以独立部署和运行的程序实体&#xff0c;独立于应用&#xff0c;不依赖应用可独立…

Redis中的String数据类型及相关命令

[经典面试题] redis虽然是单线程模型&#xff0c;为什么效率还这么高&#xff1f;速度这么快呢&#xff1f; 原因&#xff1a;1、redis主要访问内存&#xff0c;数据库则是主要访问硬盘。 2、redis的核心功能&#xff0c;比数据库的核心功能更简单。数据库对于数据的CRUD&…

远程管理不再难!树莓派5安装Raspberry Pi OS并实现使用VNC异地连接

前言&#xff1a;大家好&#xff01;今天我要教你们如何在树莓派5上安装Raspberry Pi OS&#xff0c;并配置SSH和VNC权限。通过这些步骤&#xff0c;你将能够在Windows电脑上使用VNC Viewer&#xff0c;结合Cpolar内网穿透工具&#xff0c;实现长期的公网远程访问管理本地树莓派…

本地部署 Chat Nio

本地部署 Chat Nio 0. 引言1. 本地部署2. 访问 Chat Nio3. 渠道设置4. 聊天 0. 引言 Chat Nio 的功能&#xff1a; &#x1f916;️ 丰富模型支持: 多模型服务商支持 (OpenAI / Anthropic / Gemini / Midjourney 等十余种格式兼容 & 私有化 LLM 支持)&#x1f92f; 美观 …

C# OpenCV 通过高度图去筛选轮廓

//输入图像 threshCropMap.ImWrite("D:\\test\\threshCropMap_BeforeFilterByBlob.bmp"); //设定我们要筛选的高度 var ResultHeight 60; //创建对应高度的图像&#xff0c;由于是高度信息图&#xff0c;所有要使用32位来存放数据 Mat mat new Mat(filter.Rows, fi…

23.UE5删除存档

2-25 删除存档制作_哔哩哔哩_bilibili 按照自己的风格制作删除按钮 这样该行的存档就被从存档列表中删除了&#xff0c;并且实际存档&#xff08;我的存档蓝图&#xff09;中也被删除了 但是存在一个问题&#xff0c;如果存档数据中存在索引为: 0 1 2 3的存档&#xff0c;当索…

【graphics】图形绘制 C++

众所周知&#xff0c;周知所众&#xff0c;图形绘制对于竞赛学僧毫无用处&#xff0c;所以这个文章&#xff0c;专门对相关人员教学&#xff08;成长中的码农、高中僧、大学僧&#xff09;。 他人经验教学参考https://blog.csdn.net/qq_46107892/article/details/133386358?o…

kafka基础

文章目录 一、Kafka入门1.1、JMS1.2、生产者-消费者模式1.3、ZooKeeper 二、kafka基础架构2.1、producer2.2、kafka cluster2.2.1、broker2.2.2、Controller2.2.3、Topic2.2.4、Partition2.2.5、Replication2.2.6、Leader & Follower 2.3、consumer 一、Kafka入门 Kafka是一…

PMP–一、二、三模、冲刺–分类--5.范围管理--技巧--需求跟踪矩阵

文章目录 技巧一模反例不选“需求跟踪矩阵”4.整合管理86、 [单选] 项目经理加入一个项目&#xff0c;但项目经理在该项目所涉及的行业经验有限&#xff0c;在该项目的整个生命周期中&#xff0c;项目经理精心记录每个差距、问题和不一致性。但是&#xff0c;无论项目经理如何记…

掌握Golang中的数据竞争检测:runtime/race包全面教程

掌握Golang中的数据竞争检测&#xff1a;runtime/race包全面教程 引言数据竞争问题概述数据竞争的定义数据竞争对程序的影响常见数据竞争场景 Golang runtime/race包概述runtime/race包简介启用数据竞争检测使用 go run使用 go build使用 go test 基本用法与示例单元测试中的使…

ThreadLocal父子线程、线程池数据传递解决

多线程并发数据访问&#xff0c;确保数据安全至关重要&#xff0c;常用保证数据安全的方法有对代码synchronized锁、Lock锁&#xff0c;以及基于CAS的原子类&#xff0c;这些都是通过数据共享保障数据安全的&#xff0c;今天聊一聊另一种方案ThreadLocal线程副本&#xff0c;实…

Docker 从入门到精通全攻略

一、Docker 初印象 Docker 诞生于 2013 年&#xff0c;由 dotCloud 公司发起&#xff0c;最初是一个公司内部项目。其诞生背景源于程序员们苦于应用部署环境的复杂性&#xff0c;开发、测试、部署过程中各种库的依赖纷繁复杂&#xff0c;版本差异以及测试环境与部署环境不一致等…

WordPress设置自动更新CSS版本号

WordPress 通常会在引用 CSS 文件时添加版本号参数&#xff08;?verx.x.x&#xff09;。如果版本号未更新&#xff0c;浏览器可能继续加载旧的文件。 解决方法&#xff1a;确保你在 functions.php 文件中正确加载了 CSS 文件&#xff0c;并动态更新版本号。例如在functions.p…

达梦 DG

监视器 switchover 关于达梦DG switchover的细节&#xff0c;以下是一些关键步骤和注意事项&#xff1a; • 切换前检查确认&#xff1a; • 确认数据库版本和DG架构&#xff0c;包括IP信息及切换角色前后的情况。 • 检查DG切换方式&#xff0c;是switch over还是fail ove…

c#基本数据类型占用字节长度/取值范围/对应.net类型

具体前往&#xff1a;c#基本数据类型占用字节数/取值范围/包装类-各基本类型.net类型,占用bit位数,默认值及取值范围

多品牌NVR管理工具/设备EasyNVR多个NVR同时管理支持RTSP接入

在当今数字化浪潮席卷全球的背景下&#xff0c;视频监控行业正经历着前所未有的变革。传统的本地录像存储模式正逐步向云端集中管理转型&#xff0c;这一技术的飞跃不仅极大地提升了监控效率与安全性&#xff0c;更为各行各业的智能化管理开辟了新路径。在这一转型过程中&#…

初学者指南:知识库问答(KBQA)多跳路径的核心与应用

初学者指南&#xff1a;知识库问答&#xff08;KBQA&#xff09;多跳路径的核心与应用 知识库问答&#xff08;Knowledge Base Question Answering, KBQA&#xff09;旨在利用结构化知识库&#xff08;如Wikidata、Freebase&#xff09;回答自然语言问题。在实际应用中&#x…

利用Python爬虫获取淘宝店铺详情

在数字化时代&#xff0c;数据已成为企业最宝贵的资产之一。对于电商平台&#xff0c;尤其是淘宝这样的大型电商平台&#xff0c;店铺详情数据的获取和分析对于商家来说至关重要。它不仅可以帮助商家了解市场趋势&#xff0c;还可以优化营销策略&#xff0c;提升销售业绩。本文…

卡尔曼滤波学习资料汇总

卡尔曼滤波学习资料汇总 其实&#xff0c;当初的目的&#xff0c;是为了写 MPU6050 的代码的&#xff0c;然后不知不觉学了那么多&#xff0c;也是因为好奇、感兴趣吧 有些还没看完&#xff0c;之后笔记也会同步更新的 学习原始材料 【卡尔曼滤波器】1_递归算法_Recursive P…

【HCIP]——OSPF综合实验

题目 实验需求 根据上图可得&#xff0c;实验需求为&#xff1a; 1.R5作为ISP&#xff1a;其上只能配置IP地址&#xff1b;R4作为企业边界路由器&#xff0c;出口公网地址需要通过PPP协议获取&#xff0c;并进行CHAP认证。&#xff08;PS&#xff1a;因PPP协议尚未学习&#…