leetcode:反转链表II 和k个一组反转链表的C++实现
反转链表II
问题描述
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode *newhead = new ListNode(0);newhead->next = head;int i = 1;ListNode* pre = newhead;while(i < left){pre = pre->next;i++;}ListNode* cur = pre->next;ListNode* pnext;while(i < right and cur){pnext = cur->next;cur->next = pnext->next;pnext->next = pre->next;pre->next = pnext;i++;}return newhead->next;
}
这段代码定义了一个函数 reverseBetween,该函数的目的是反转一个单链表中从位置 left 到位置 right 的部分链表。链表的节点定义采用 ListNode 结构。
函数参数和返回值
- 参数
ListNode* head是指向链表第一个节点的指针。 - 参数
int left是需要开始反转的起始位置。 - 参数
int right是需要结束反转的终止位置。 - 返回值
ListNode*是指向经过部分反转后的链表的头节点的指针。
函数内部逻辑
- 创建一个新的头节点
newhead,其值为0,并将其next指针指向原链表的头节点head。这是为了方便处理边界情况,特别是当left为1时。 - 初始化一个计数器
i为1,用于记录当前的位置。 - 初始化一个指针
pre,它将用于跟踪第left-1个节点,即反转部分的前一个节点。 - 使用
while循环将pre指针移动到第left-1个节点的位置。 - 初始化另一个指针
cur,它将用于跟踪当前要进行反转操作的节点,初始时指向第left个节点。 - 使用另一个
while循环,在i小于right时进行反转操作,并确保cur不为空:- 将
pnext指向cur的下一个节点。 - 将
cur的next指针指向pnext的下一个节点,这样就从链表中断开了pnext。 - 将
pnext的next指针指向pre的下一个节点,这样pnext就移动到了反转部分的开始位置。 - 将
pre的next指向pnext,这样就将pnext插入到了反转部分的开始位置。 - 增加计数器
i。
- 将
- 循环结束后,从位置
left到位置right的链表部分已经被反转。 - 返回
newhead->next,即新链表的头节点,因为newhead是一个哑节点。
总结
此代码通过迭代的方式,反转了单链表的一部分。它首先使用一个哑节点简化操作,然后通过两个循环移动节点,逐步实现链表的局部反转。最终返回新链表的头节点。
k个一组反转链表
问题描述
以 k 个节点为一组进行链表翻转,即每 k 个节点之内进行翻转,如果最后一组不足 k 个节点,则不进行翻转。
解决方案
以下是 C++ 代码实现:
ListNode* reverseKGroup(ListNode* head, int k) {if (head == nullptr || k == 1) {return head;}ListNode* dummy = new ListNode(0);dummy->next = head;ListNode *pre = dummy, *cur = dummy, *nex = dummy;int count = 0;// 计算链表长度while (cur->next != nullptr) {cur = cur->next;count++;}// 根据链表长度计算需要翻转的次数while (count >= k) {cur = pre->next; // 重置当前节点为组的第一个节点nex = cur->next; // 重置下一个节点// 进行 k-1 次翻转for (int i = 1; i < k; i++) {cur->next = nex->next;nex->next = pre->next;pre->next = nex;nex = cur->next;}pre = cur; // 将 pre 移动到下一组的开始位置count -= k; // 减少 k 个计数}return dummy->next;
}
这段代码定义了一个函数 reverseKGroup,用于按照给定的大小 k 反转一个单链表中的节点组。反转是以每 k 个节点为一组进行的,最后不足 k 个节点的组不会被反转。
函数参数和返回值
- 参数
ListNode* head是指向链表第一个节点的指针。 - 参数
int k是每组中的节点数量。 - 返回值
ListNode*是指向经过分组反转后的链表的头节点的指针。
函数内部逻辑
- 首先检查是否需要进行操作,如果链表为空 (
nullptr) 或k等于1(即不需要分组反转),则直接返回原链表的头节点head。 - 创建一个哑节点
dummy,其值为0,并将其next指针指向原链表的头节点head。这是为了方便操作,特别是当链表的头部需要被反转时。 - 初始化三个指针
pre、cur和nex,它们都指向哑节点dummy。pre将用于跟踪每组反转前的第一个节点的前一个节点,cur将用于遍历链表,而nex将用于反转操作中的节点交换。 - 初始化计数器
count为0,用于记录链表的长度。 - 使用
while循环计算链表的长度,并将长度存储在count中。 - 使用另一个
while循环,只要count大于或等于k,就执行以下操作:- 重置
cur为当前组的第一个节点,即pre的下一个节点。 - 重置
nex为cur的下一个节点。 - 进行
k-1次反转操作,因为每组的第一个节点不需要移动,只需移动剩余的k-1个节点:- 将
cur的next指向nex的下一个节点,这样就从链表中断开了nex。 - 将
nex的next指向pre的下一个节点,这样nex就移动到了当前组的开始位置。 - 将
pre的next指向nex,这样就将nex插入到了当前组的开始位置。 - 更新
nex为cur的下一个节点,为下一次迭代做准备。
- 将
- 在完成一组节点的反转后,将
pre移动到这组的最后一个节点,即当前的cur,准备进行下一组的反转。 - 从
count中减去k,表示已经完成了一组节点的反转。
- 重置
- 循环结束后,所有的
k个节点的组都已经被反转,不足k个节点的组保持原样。 - 返回
dummy->next,即新链表的头节点,因为dummy是一个哑节点。
总结
此代码通过迭代的方式,每次反转链表中的 k 个节点。它首先使用一个哑节点简化操作,然后通过两个循环,一是计算链表长度,二是进行分组反转。最终返回新链表的头节点。
相关文章:
leetcode:反转链表II 和k个一组反转链表的C++实现
反转链表II 问题描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left < right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode *…...
ERD Online 快速启动指南:代码下载到首次运行的全流程攻略 ️
🚀 一、代码下载 ERD online前端代码正常拉取即可👌 后端代码含有子模块,拉取命令如下: git clone --recurse-submodules https://github.com/www-zerocode-net-cn/martin-framework.git 🛠️ 二、代码构建 dz…...
c++ 11 新特性 不同数据类型之间转换函数之const_cast
一.不同数据类型之间转换函数const_cast介绍 const_cast是C11中引入的一种类型转换操作符,用于修改类型的const或volatile属性。const_cast的主要用途是移除对象的常量性,它是唯一具有此能力的C风格的转型操作符。在C11中,const_cast可以完成…...
C++从零开始的打怪升级之路(day45)
这是关于一个普通双非本科大一学生的C的学习记录贴 在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料 那么开启正题 今天分享的是关于二叉树的题目 1.根据二叉树创建字符串 606. 根…...
小鹅通前端实习一面
总时长35分钟,自我介绍开始 1.js和c特点上的差异; 2.js数组去重 3.js的数据类型 4.js的引用类型和值类型的差别 5.讲一下js的网络请求 6.对前端三件套和框架的理解 7.一个html文档的结构是怎样的 8.head和body的区别 9.一个页面的加载顺序(ht…...
ArrayList常用API
常见方法 add 增remove 删set 改get 查clear 清空元素size 长度isEmpty 为空判断 用法 // String就是泛型 这种使用方法对于限制类型很有用 ArrayList<String> arrayList new ArrayList<>();// add 添加元素 返回的是boolean 代表是否添加成功 arrayList.add(&qu…...
Chrome安装Axure插件
打开原型目录/resources/chrome,重命名axure-chrome-extension.crx,修改后缀为rar,axure-chrome-extension.rar 解压到axure-chrome-extension目录打开Chrome,更多工具->扩展程序,打开开发者模式,选择加…...
【AI+应用】模仿爆款视频二次创作短视频操作步骤
本来不想水这篇的, 剪辑软件估计很多人用的比我还6。 今天自己遇到1个需求,我看到一篇公众号文章的视频觉得有意思,但视频有点长,我没带耳机看视频的习惯,就想着能不能下载下来, 提取视频的音频转为文字&am…...
HTML使用
文章目录 一、简介二、HTML快速入门三、基础标签四、图片、音频、视频标签五、超链接标签六、列表标签七、表格标签八、布局标签九、表单标签十、表单向标签 一、简介 二、HTML快速入门 <html><head><title>你好</title></head><body>再…...
通过联合部署DDoS高防和WAF提升网站防护能力
如果您的网站遭受的攻击既有流量型攻击,又混杂精巧的Web应用层攻击时(例如SQL注入、跨站脚本攻击、命令注入等)时,推荐您组合使用阿里云DDoS高防和Web 应用防火墙 WAF(Web Application Firewall)࿰…...
具体挫折现象的发生以及解法思考:您如果继续不问的话,严重重责就容易来
一 积极想方设法的寻找扭转劣势的方式方法; 目前对于第一条的践行,主要还是依靠打工做事赚取收入。至于个人业务,只能往后推,往后延迟。因为不管您目前居住的环境,还是个人条件都不行,所以无法实行个人业…...
Type-C接口PD协议统一:引领电子科技新纪元的优势解析
在电子科技日新月异的今天,充电接口的统一化已经成为了业界的一大趋势。其中,Type-C接口凭借其传输速度快、使用便捷等优点,迅速成为了市场上的主流选择。而PD(Power Delivery)协议的统一,更是为Type-C接口…...
探讨2024年AI辅助研发的趋势
一、引言 随着科技的飞速发展,人工智能(AI)已经成为当今时代最具变革性的技术之一。AI的广泛应用正在重塑各行各业,其中,AI辅助研发作为科技和工业领域的一大创新热点,正引领着研发模式的深刻变革。从医药…...
Java对接海康威视摄像头实现抓图
目录 一、下载SDK 二、拷贝示例代码 三、拷贝库文件 四、运行Demo 五、抓图业务 六、调参 七、发布Linux正式环境 一、下载SDK 海康开放平台 二、拷贝示例代码 三、拷贝库文件 这时候直接运行ClientDemo会报错,因为缺失库文件! 四、运行Demo …...
浏览器一键重新发起请求
一、需求场景 在前端开发过程中,经常会需要重新请求后台进行代码调试,之前的常规方法是刷新浏览器页面或者点击页面进行交互,这样对多个请求的场景就很方便,但是往往很多时候我们只是单纯的想重新发起一个请求(多个请求…...
一起来读李清照
当然先祝各位女生节日快乐🎁🎁啦。 但是呢,今天,我们不聊技术,来聊点其他的。 大家都知道今天是三八妇女节,三八妇女节的是中国人的叫法,也叫国际妇女节。是为了纪念妇女权利的运动&#…...
找出单身狗1,2
目录 1. 单身狗12. 单身狗2 1. 单身狗1 题目如下: 思路:一部分人可能会使用对数组排序,遍历数组的方式去找出只出现一次的数字,但这种方法的时间复杂度过高,有时候可能会不满足要求。 有一种十分简便的方法是使用异或…...
贝叶斯优化BiLSTM分类预测(matlab代码)
贝叶斯优化BiLSTM分类matlab代码 数据为Excel分类数据集数据。 数据集划分为训练集、验证集、测试集,比例为8:1:1 数据处理: 在数据加载后,对数据进行了划分,包括训练集、验证集和测试集,这有助于评估模型的泛化能力。 数据标…...
Linux运维:实现光盘开机自动挂载、配置本地yum源教程
Linux运维:实现光盘开机自动挂载、配置本地yum源教程 一、光盘开机自动挂载1、检查光驱设备2、创建挂载点3、编辑/etc/fstab文件4、测试挂载 二、配置本地yum源(挂载光盘或ISO文件)1、挂载ISO文件2、创建YUM仓库配置文件3、清理YUM缓存并测试 💖The Begi…...
C语言从入门到精通 第十二章(程序的编译及链接)
写在前面: 本系列专栏主要介绍C语言的相关知识,思路以下面的参考链接教程为主,大部分笔记也出自该教程。除了参考下面的链接教程以外,笔者还参考了其它的一些C语言教材,笔者认为重要的部分大多都会用粗体标注…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
