力扣第92题——反转链表 II(C语言题解)

题目描述

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

示例 1:

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

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

方法一:穿针引线

我们以下图中黄色区域的链表反转为例。

使用「206. 反转链表」的解法,反转 left 到 right 部分以后,再拼接起来。我们还需要记录 left 的前一个节点,和 right 的后一个节点。如图所示:

算法步骤:

第 1 步:先将待反转的区域反转;
第 2 步:把 pre 的 next 指针指向反转以后的链表头节点,把反转以后的链表的尾节点的 next 指针指向 succ。

说明:编码细节我们不在题解中介绍了,请见下方代码。思路想明白以后,编码不是一件很难的事情。这里要提醒大家的是,链接什么时候切断,什么时候补上去,先后顺序一定要想清楚,如果想不清楚可以在纸上模拟.

void reverseLinkedList(struct ListNode *head) {
    // 也可以使用递归反转一个链表
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;

    while (cur != NULL) {
        struct ListNode *next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
}

struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
    // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
    struct ListNode *dummyNode = malloc(sizeof(struct ListNode));
    dummyNode->val = -1;
    dummyNode->next = head;

    struct ListNode *pre = dummyNode;
    // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
    // 建议写在 for 循环里,语义清晰
    for (int i = 0; i < left - 1; i++) {
        pre = pre->next;
    }

    // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
    struct ListNode *rightNode = pre;
    for (int i = 0; i < right - left + 1; i++) {
        rightNode = rightNode->next;
    }

    // 第 3 步:切断出一个子链表(截取链表)
    struct ListNode *leftNode = pre->next;
    struct ListNode *curr = rightNode->next;

    // 注意:切断链接
    pre->next = NULL;
    rightNode->next = NULL;

    // 第 4 步:同第 206 题,反转链表的子区间
    reverseLinkedList(leftNode);

    // 第 5 步:接回到原来的链表中
    pre->next = rightNode;
    leftNode->next = curr;
    return dummyNode->next;
}

 

方法二:一次遍历「穿针引线」反转链表(头插法)

方法一的缺点是:如果 left 和 right 的区域很大,恰好是链表的头节点和尾节点时,找到 left 和 right 需要遍历一次,反转它们之间的链表还需要遍历一次,虽然总的时间复杂度为 O(N)O(N)O(N),但遍历了链表 222 次,可不可以只遍历一次呢?答案是可以的。我们依然画图进行说明。

我们依然以方法一的示例为例进行说明。

整体思想是:在需要反转的区间里,每遍历到一个节点,让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量,它们的意义如下:

curr:指向待反转区域的第一个节点 left;
next:永远指向 curr 的下一个节点,循环过程中,curr 变化以后 next 会变化;
pre:永远指向待反转区域的第一个节点 left 的前一个节点,在循环过程中不变。
第 1 步,我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤:

先将 curr 的下一个节点记录为 next;
执行操作 ①:把 curr 的下一个节点指向 next 的下一个节点;
执行操作 ②:把 next 的下一个节点指向 pre 的下一个节点;
执行操作 ③:把 pre 的下一个节点指向 next。
第 1 步完成以后「拉直」的效果如下:

第 2 步,同理。同样需要注意 「穿针引线」操作的先后顺序。

第 2 步完成以后「拉直」的效果如下:

第 3 步,同理。

第 3 步完成以后「拉直」的效果如下:

struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
    // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
    struct ListNode *dummyNode = malloc(sizeof(struct ListNode));
    dummyNode->val = -1;
    dummyNode->next = head;

    struct ListNode *pre = dummyNode;
    for (int i = 0; i < left - 1; i++) {
        pre = pre->next;
    }
    struct ListNode *cur = pre->next;
    struct ListNode *next;
    for (int i = 0; i < right - left; i++) {
        next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }
    return dummyNode->next;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

精品基于Uniapp+springboot智慧农业环境监测App

《[含文档PPT源码等]精品基于Uniappspringboot智慧农业环境监测App》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功&#xff01; 软件开发环境及开发工具&#xff1a; 开发语言&#xff1a;Java 后台框架&#xff1a;springboot、ssm …

Android双指缩放ScaleGestureDetector检测放大因子大图移动到双指中心点ImageView区域中心,Kotlin

Android双指缩放ScaleGestureDetector检测放大因子大图移动到双指中心点ImageView区域中心&#xff0c;Kotlin 在 Android双击图片放大移动图中双击点到ImageView区域中心&#xff0c;Kotlin-CSDN博客 基础上&#xff0c;这次使用ScaleGestureDetector检测两根手指的缩放动作&a…

一起玩儿物联网人工智能小车(ESP32)——44. 利用红外测距模块GP2Y0E03实现避障小车

摘要&#xff1a;本文介绍使用红外测距模块GP2Y0E03实现避障小车 在前边已经介绍了两种非接触测距的办法&#xff0c;分别是超声波测距和激光测距&#xff0c;在这里&#xff0c;再介绍另一种常用的测距传感器——红外测距传感器。红外测距的工作原理是&#xff0c;利用红外信号…

HuoCMS|免费开源可商用CMS建站系统HuoCMS 2.0下载(thinkphp内核)

HuoCMS是一套基于ThinkPhp6.0Vue 开发的一套HuoCMS建站系统。 HuoCMS是一套内容管理系统同时也是一套企业官网建设系统&#xff0c;能够帮过用户快速搭建自己的网站。可以满足企业站&#xff0c;外贸站&#xff0c;个人博客等一系列的建站需求。HuoCMS的优势: 可以使用统一后台…

数学建模--Radar图绘制

1.Radar图简介 最近在数学建模中碰见需要绘制Radar图(雷达图)的情况来具体分析样本的各个特征之间的得分与优劣关系&#xff0c;这样的情况比较符合雷达图的使用场景&#xff0c;一般来说&#xff0c;雷达图适用于展示多个维度的数据&#xff0c;并在一个平面上直观地呈现出不同…

前端每日一练 “文字穿透效果”

前言 我都不知道用什么样的词来描述这个效果&#xff0c;反正你看吧&#xff01;这个效果看上去很简单&#xff0c;但是一旦实现起来你会发现也不复杂&#xff0c;废话不多说直接上源码&#xff0c;喜欢的点个关注、留个免费的 html源码 <!DOCTYPE html> <html>&…

13.8.1异步、异步、异步 Page720~721

#include <iostream> #include <thread> #include <future>using namespace std;///定时炸弹第一波 void sync_sleep(int s) {cout << "sync_sleep----不使用异步" << endl;///启动定时this_thread::sleep_for(chrono::seconds(s)); /…

《WebKit 技术内幕》学习之十(2): 插件与JavaScript扩展

2 Chromium PPAPI插件 2.1 原理 插件其实是一种统称&#xff0c;表示一些动态库&#xff0c;这些动态库根据定义的一些标准接口可以跟浏览器进行交互&#xff0c;至于这个标准接口是什么都可以&#xff0c;重要的是大家都遵循它们&#xff0c;NPAPI接口标准只是其中的一种&a…

FastDFS分布式文件存储

为什么会有分布式文件系统&#xff1f; 分布式文件系统是面对互联网的需求而产生。因为互联网时代要对海量数据进行存储。很显然靠简单的增加硬盘个数已经满足不了我们的要求。因为硬盘传输速度有限但是数据在急剧增长&#xff0c;另外我们还要要做好数据备份、数据安全等。采用…

初识k8s(概述、原理、安装)

文章目录 概述由来主要功能 K8S架构架构图组件说明ClusterMasterNodekubectl 组件处理流程 K8S概念组成PodPod控制器ReplicationController&#xff08;副本控制器&#xff09;ReplicaSet &#xff08;副本集&#xff09;DeploymentStatefulSet &#xff08;有状态副本集&#…

6 时间序列(不同位置的装置如何建模): GRU+Embedding

很多算法比赛经常会遇到不同的物体产生同含义的时间序列信息&#xff0c;比如不同位置的时间序列信息&#xff0c;风力发电、充电桩用电。经常会遇到该如此场景&#xff0c;对所有数据做统一处理喂给模型&#xff0c;模型很难学到区分信息&#xff0c;因此设计如果对不同位置的…

【Linux】常见指令(一)

前言: Linux有许多的指令&#xff0c;通过学习这些指令&#xff0c;可以对目录及文件进行操作。 文章目录 一、基础指令1. ls—列出目录内容2. pwd—显示当前目录3. cd—切换目录重新认识指令4. touch—创建文件等5. mkdir—创建目录6. rmdir指令 && rm 指令7. man—显…

linux源码编译安装llvm

目录 1 建立文件夹llvm 2 下载源码到llvm文件夹 3 解压上述文件 4 将解压后的3个文件夹改名&#xff0c;并移动到llvm-9.0.0.src中&#xff1a; 5 在llvm文件夹内建立build文件夹&#xff0c;并进入该文件夹&#xff1a; 6 执行cmake命令 7 make 8 安装 9 安装成功后…

[晓理紫]每日论文分享(有中文摘要,源码或项目地址)--机器人、强化学习

专属领域论文订阅 VX 扫吗关注{晓理紫|小李子}&#xff0c;每日更新论文&#xff0c;如感兴趣&#xff0c;请转发给有需要的同学&#xff0c;谢谢支持 如果你感觉对你有帮助可以扫吗关注&#xff0c;每日准时为你推送最新论文 分类: 大语言模型LLM视觉模型VLM扩散模型视觉导航…

Git Docker 学习笔记

注意&#xff1a;该文章摘抄之百度&#xff0c;仅当做学习笔记供小白使用&#xff0c;若侵权请联系删除&#xff01; 目录 列举工作中常用的几个git命令&#xff1f; 提交时发生冲突&#xff0c;你能解释冲突是如何产生的吗&#xff1f;你是如何解决的&#xff1f; git的4个…

安全通信网络

1.网络架构 1&#xff09;应保证网络设备的业务处理能力满足业务高峰期需要。 设备CPU和内存使用率的峰值不大于设备处理能力的70%。 在有监控环境的条件下&#xff0c;应通过监控平台查看主要设备在业务高峰期的资源&#xff08;CPU、内存等&#xff09;使用 情况&#xff…

双数据源同步的思考

双数据源同步的思考 目录概述需求&#xff1a; 设计思路实现思路分析1.简单实现 2.Spring mybatis 技术 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy&#xff0c;skip hardness,make a better result,wa…

geemap学习笔记053:纹理特征

前言 纹理特征通常描述了遥感影像中像素之间的空间关系和变化&#xff0c;对于地物分类、目标检测以及图像分割等遥感应用非常有价值。本节将会介绍Earth Engine中提供的一些纹理特征计算方法&#xff0c;包括熵和灰度共生矩阵。 1 导入库并显示数据 import ee import geema…

.NET发展如火如荼,这回.Net 8的野心确实不小

随着三天.NET Conf 2023的会议结束了&#xff0c;.Net 8正式发布了。 .Net 8是官方号称有史以来性能最快的一个版本了。 .Net 8 增加了数以千计的性能、稳定性和安全性改进&#xff0c;以及平台和工具增强功能&#xff0c;有助于提高开发人员的工作效率和创新速度。 反正就是快…

【Leetcode 965.】判断单值二叉树

单值二叉树&#xff1a; 示例一&#xff1a; 示例二&#xff1a; 代码&#xff1a; bool isUnivalTree(struct TreeNode* root) {if(rootNULL)return true;if(root->left&&root->left->val!root->val)return false;if(root->right&&root-&…