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

ops/2024/11/26 1:19:25/

目录

申明

 题目

头插法解题        

步骤图解

程序解析


申明

        该题源自力扣题库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;
};

        题目内容到此位置,题目意思应该很好理解,在上篇文章中我们的解题思路主要是选将需要反转的链表拆出来,如何将其反转,最后接回去。虽然功能实现了,但在这个过程中我们也发现过程不是很顺利,一个是需要两次遍历,切链表的时候遍历一次,反转链表的时候遍历一次;其次是因为需要大量指针,为了实现单链表的反转就需要三个指针,为了链表的拆和接也需要四个指针。

头插法解题        

        如果看过我之前的文章的话或许会发现,其实我在将单链表的建立的时候就提到过反转链表的方法-头插法。当时我们讲到链表的建立有两种方法,一个是头插法,一个是尾插法。头插法即每一个新结点都插入到头结点之后,因此后插的结点会在先插的结点前面实现链表的反转。

        类似的,我们也可以用头插法反转链表,首先我们在找到left的前驱结点

         然后遍历链表的left-right,如示例,此时我们将结点3插入到1之后(2已经在1之后了,不需要再插了)。这次插入的目标是得到这个

         观察上下两幅图,我们需要做的是

  • 将1的next指向3
  • 将3的next指向2
  • 将2的next指向4

        这是我们要的效果,但在实际操作中要十分注意你的操作顺序,这里涉及到三个结点,且要对每个结点的next都进行改变,同样的,我们也要用三个指针去操作,我们引入两个新指针start和next

        然后我们开始将3,插入到1后面,我们先分析一下next修改的顺序,有顺序的原因是因为自己要修改的next要先给到别人使用,因此我们分析一下这三个结点的next关系:

  • 1的next要给3
  • 2的next不要了
  • 3的next要给2

        我们发现2的next没用,因此我们先修改2的next(将3的next给2);此时3的next已经给过2了,因此接下来就修改3的next(将1的next给3);最后我们修改1的next,直接指向3.所以我们的修改顺序为:

  1. 修改2的next,将3的next给2
  2. 修改3的next,将1的next给3
  3. 修改1的next,将1的next指向3

用指针来表述就是:

  1. start->next=then->next;
  2. then->next=prev->next;
  3. prev->next=then;
步骤图解

1.修改start的next

2.修改3的next

3.修改1的next 

        看着是不是很别扭,没事我们跟着箭头把它拉直

        拉直之后就是这样了,是不是就插进来了。接下来对后续结点重复相同的步骤即可。

        这里需要注意的遍历,不知道你们有没有发现,就在链表的位序而言,start和then位置已经交换了,其实start已经可以视为向前一位了,遍历的时候只需要更改then指向4即可,也就是then=start->next.

程序解析
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {// 创建一个虚拟头节点struct ListNode dummy;dummy.next = head;struct ListNode *prev = &dummy;// 找到第left-1个节点for (int i = 0; i < left - 1; ++i) {prev = prev->next;}// 开始反转从left到right的部分struct ListNode *start = prev->next;//初始化start指向leftstruct ListNode *then = start->next;//初始化then指向rightfor (int i = 0; i < right - left; ++i) {//遍历需要反转部分链表start->next = then->next;then->next = prev->next;prev->next = then;then = start->next;}return dummy.next;
}

建议各位在草稿纸上跟着程序结合例题,操作一遍会更加清晰,特别是反转链表那一部分。


http://www.ppmy.cn/ops/136720.html

相关文章

Github工作流

GitHub 工作流 是一种专门为 GitHub 上的代码协作和版本控制而设计的工作流&#xff0c;它强调通过 **拉取请求&#xff08;Pull Request&#xff0c;PR&#xff09;** 来管理代码的合并和审查。GitHub 工作流通常涉及到使用 **分支** 来进行功能开发和修复&#xff0c;并通过 …

Linux---ps命令

​​​​​​Linux ps 命令 | 菜鸟教程 (runoob.com) process status 用于显示进程的状态 USER: 用户名&#xff0c;运行此进程的用户名。PID: 进程ID&#xff08;Process ID&#xff09;&#xff0c;每个进程的唯一标识号%CPU: 进程当前使用的CPU百分比%MEM: 进程当前使用的…

SpringBoot 集成 html2Pdf

一、概述&#xff1a; 1. springboot如何生成pdf&#xff0c;接口可以预览可以下载 2. vue下载通过bold如何下载 3. 一些细节&#xff1a;页脚、页眉、水印、每一页得样式添加 二、直接上代码【主要是一个记录下次开发更快】 模板位置 1. 导入pom包 <dependency><g…

Java技术分享

剖析equals方法 1、对于Object来说&#xff0c;其equals()方法底层实现就是""&#xff0c;都是比较对象的引用是否相等&#xff0c;下为JDK源码。 Object c 1; Object d 1; boolean equals c.equals(d);public boolean equals(Object obj) {return (this obj);…

贪心算法(2)

目录 K次取反后最大化的数组和 题解&#xff1a; 代码&#xff1a; 按身高排序&#xff08;田忌赛马的预备&#xff09; 题解&#xff1a; 代码&#xff1a; 方法一&#xff1a; 方法二&#xff1a; 优势洗牌&#xff08;田忌赛马&#xff09; 题解&#xff1a; 代…

debian下查看端口号命令

在 Debian 操作系统下,你可以使用以下命令来查看正在使用的端口号: 使用 netstat​:你可以使用 ​​netstat​​ 命令结合 ​​grep​​ 来查看特定的端口或协议。需要先安装 ​​net-tools​​,因为在一些现代系统上它可能默认未安装。sudo apt update sudo apt install n…

Three.js 相机控制器Controls

在 3D 场景中&#xff0c;摄像机的控制尤为重要&#xff0c;因为它决定了用户如何观察和与场景互动。Three.js 提供了多种相机控制器&#xff0c;最常用的有 OrbitControls、TrackballControls、FlyControls 和 FirstPersonControls。OrbitControls 适合用于查看和检查 3D 模型…

对元素为 pair 的数组的各元素进行排序的方法

【知识点】 ● 按结构体某一字段对结构体数组进行排序https://blog.csdn.net/hnjzsyjyj/article/details/120184972 据此知识点&#xff0c;则可构建 pair 元素数组的自定义排序代码如下所示。 typedef pair<int,int> PII;int up(PII u,PII v) { //ascending by firstif…