当前位置: 首页 > news >正文

BM2 链表内指定区间反转,为什么链表要new一个结点?

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

思路就是,把需要反转的结点放入栈中,然后在弹出来。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/#include<stack>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;//前一个结点ListNode* cur = head;//当前节点ListNode* res = head;//如果从头节点开始反转,需要重新弄一个头节点以便返回iListNode* tmp = head;//临时结点ListNode T(0);if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}ListNode*T = new ListNode(s.top());res = T;tmp = res;s.pop();while (!s.empty()){ListNode*T = new ListNode(s.top());tmp->next = T;s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;tmp=cur;cur = cur->next;}return res;}else{while (cnt != m)//这个while世找到m{cnt++;pre = cur;cur = cur->next;}while (cnt <=  n)//入栈{s.push(cur->val);cnt++;cur = cur->next;}//cout<<cur->val<<endl;while (!s.empty())//重新连接{//cout<<s.top()<<endl;ListNode*T = new ListNode(s.top());pre->next = T;s.pop();pre = pre->next;//cout<<pre->val<<endl;}//cout<<pre->val<<endl;while (cur)//连n之后的{pre->next = cur;pre=cur;//cout<<pre->val<<endl;cur = cur->next;}return head;}// write code here}
};

下面有一个错误代码,与上面不一的地方在于

class Solution {
public:ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;ListNode* cur= head;ListNode *res=head;ListNode* tmp=head;if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}res = &ListNode(s.top());tmp = res;s.pop();while (!s.empty()){tmp->next = &ListNode(s.top());s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;cur = cur->next;}return res;}else{while (cnt != m){cnt++;pre = cur;cur = cur->next;}while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}while (!s.empty()){pre->next = &ListNode(s.top());s.pop();pre = pre->next;}while (cur){tmp->next = cur;cur = cur->next;}return head;}// write code here}
}
/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/#include<stack>
ListNode T(0);
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;ListNode* cur = head;ListNode* res = head;ListNode* tmp = head;//ListNode T(0);if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}T=ListNode(s.top());res = &T;tmp = res;s.pop();while (!s.empty()){T=ListNode(s.top());tmp->next = &T;s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;cur = cur->next;}return res;}else{while (cnt != m){cnt++;pre = cur;cur = cur->next;}while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}//cout<<cur->val<<endl;while (!s.empty()){//cout<<s.top()<<endl;T=ListNode(s.top());pre->next = &T;s.pop();pre = pre->next;//cout<<pre->val<<endl;}//cout<<pre->val<<endl;while (cur){pre->next = cur;pre=cur;//cout<<pre->val<<endl;cur = cur->next;}return head;}// write code here}
};

 

 一个是new一个结点,另一个是建一个结点然后取地址,错误的代码在于,

就是错误代码,我想的是自己创的局部变量T,这个对象每次都是新的,结果在VS2022上调试,一步步发现,原来每次新建的T居然是一个地址!!因为链表里已经加入了之前的T的这个地址,这直接导致链表发生错误,以第一个用例为例,本意是想实现1-4-3-2,结果最后只有1-2

因为在循环时,首先是1-4,在创建3这个节点时,由于是4的地址,所以就把4覆盖了,输出1-3,而不是1-4-3.
链表申请新节点要new。这样每次地址都不一样就连起来了。



下面讲一种,加入一个虚拟节点(哨兵)的做法,之所以这样是可以当从头节点开始转变时,代码不用特判。

 

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode* res=new ListNode(0);//虚拟节点res->next=head;ListNode* pre=res;ListNode* cur=head;ListNode* beg=head;ListNode* en=head;ListNode* tmp;for(int i=1;i<m;i++){pre=beg;beg=beg->next;}for(int i=1;i<n;i++){en=en->next;}cur=beg->next;beg->next=en->next;pre->next=en;pre=beg;while(pre!=en){tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return res->next;// write code here}
};

第三个方法

 

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode* res=new ListNode(0);//虚拟节点res->next=head;ListNode* pre=res;ListNode* cur=head;ListNode* beg=head;ListNode* tmp;for(int i=1;i<m;i++){pre=beg;beg=beg->next;}tmp=beg->next;for(int i=m+1;i<=n;i++){cur=tmp;tmp=tmp->next;beg->next=tmp;cur->next=pre->next;pre->next=cur;}return res->next;// write code here}
};



 


 

 

相关文章:

BM2 链表内指定区间反转,为什么链表要new一个结点?

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com) 思路就是&#xff0c;把需要反转的结点放入栈中&#xff0c;然后在弹出来。 /*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/#include<stack> class…...

SQL阶段性优化

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;MySQL、SQL优化、阶段性优化☀️每日 一言&#xff1a;我们要把懦弱扼杀在摇篮中。 一、前言 我们在做系统的过程中&#xff0c;难免会遇到页面查询速度慢&#xff0c;性能差的问题&#xff0c;…...

2023-08-22 Unity Shader 开发入门2 —— Shader 开发介绍

文章目录 一、必备概念1 计算机图形程序接口2 图形接口程序与其他概念的联系 二、Shader 开发1 Shader2 Shader 开发3 需掌握的内容 一、必备概念 1 计算机图形程序接口 ​ 计算机图形程序接口&#xff08;Graphics API&#xff09;是一套可编程的开放标准&#xff0c;不论 2…...

UE5 运行时捕捉外部窗口并嵌入到主窗口

UE5 运行时捕捉外部窗口并嵌入到主窗口的一种方法 创建一个Slate类用于生成一个窗口 .h// Fill out your copyright notice in the Description page of Project Settings.#pragma once#include "CoreMinimal.h" #include "Widgets/SCompoundWidget.h"/*…...

uniapp 使用permission获取录音权限

使用前&#xff0c;需要先配置权限 android.permission.RECORD_AUDIO...

基于paddleocr的文档识别

1、版面分析 使用轻量模型PP-PicoDet检测模型实现版面各种类别的检测。 数据集&#xff1a; 英文&#xff1a;publaynet数据集的训练集合中包含35万张图像&#xff0c;验证集合中包含1.1万张图像。总共包含5个类别。 中文&#xff1a;CDLA据集的训练集合中包含5000张图像&a…...

魏副业而战:闲鱼卖货赚钱策略

我是魏哥&#xff0c;与其躺平&#xff0c;不如魏副业而战&#xff01; 闲鱼卖货有人赚钱&#xff0c;有人不赚钱。 什么原因呢&#xff1f;闲鱼卖货的策略不对。 这不&#xff0c;社群成员小K找我反馈40单赚了150。 利润太低&#xff0c;不在正常范围之内。 魏哥建议继续…...

语法篇--XML数据传输格式

一、XML概述 1.1简介 XML&#xff0c;全称为Extensible Markup Language&#xff0c;即可扩展标记语言&#xff0c;是一种用于存储和传输数据的文本格式。它是由W3C&#xff08;万维网联盟&#xff09;推荐的标准&#xff0c;广泛应用于各种系统中&#xff0c;如Web服务、数据…...

【Redis】缓存雪崩、缓存击穿、缓存穿透

在使用 Redis 缓存时&#xff0c;常常会遇到三个主要的问题&#xff0c;分别是缓存雪崩、缓存击穿和缓存穿透。这些问题都可能导致缓存系统的性能下降或数据不一致性的问题。 一、缓存雪崩&#xff08;Cache Avalanche&#xff09; 缓存雪崩是指在某个时间点&#xff0c;缓存…...

通过示例学习 JavaScript 运算符 - 逻辑、比较、三元和更多 JS 运算符

JavaScript 有许多运算符,可用于对值和变量(也称为操作数)执行操作 根据这些 JS 运算符执行的操作类型,我们可以将它们分为七组: 目录 算术运算符赋值运算符比较运算符逻辑运算符三元运算符typeof操作员按位运算符 算术运算符 1. 加法运算符 2.减法运算符 3. 乘法运…...

基于微信小程序+Springboot校园二手商城系统设计和实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、目前专注于大学生项目实战开发,讲解,毕业答疑辅导✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3…...

excel 动态表头与合并列

零、希望Springboot-java导出excel文件&#xff0c;包括动态表头与下边合并的列 使用 org.apache.poi 与自己封装工具类实现相关功能。代码如下 一、代码 1、依赖 implementation(group: org.apache.poi,name: poi-ooxml,version: 4.1.0)implementation(group: org.apache.po…...

jenkins自动部署微服务到docker

1、代码上传到git&#xff1b; 2、jenkins拉取git的代码&#xff0c;maven打包&#xff0c;使用插件生成镜像&#xff0c;自动上传docker&#xff1b; 两个插件&#xff0c;一个打包插件&#xff0c;一个创建镜像上传docker仓库.&#xff08;将dockerfile内容搬到插件配置&…...

【蔚来汽车】蔚来20220713第三题-旅游规划 <模拟、滑动窗口>

【蔚来汽车】蔚来20220713第三题-旅游规划 牛牛对 n 个城市旅游情况进行了规划&#xff0c;已知每个城市有两种属性 x 和 y &#xff0c;其中 x 表示去第 i 号城市的花费&#xff0c;y 表示在第 i 号城市游玩后会得到的开心值。   现在牛牛希望从中挑选出一些城市去游玩&…...

[解决方案]Antd TreeSelect/Select placeholder失效

&#x1f50e;嘿&#xff0c;这里是慰慰&#x1f469;&#x1f3fb;‍&#x1f393;&#xff0c;会发各种类型的文章&#xff0c;智能专业&#xff0c;从事前端&#x1f43e; &#x1f389;如果有帮助的话&#xff0c;就点个赞叭&#xff0c;让我开心一下&#xff01;&#x1f…...

微人事 部门管理 模块 (十五)

部门管理的树展示和搜索 数据展示页是个树&#xff0c;我们一次性把数据加载出来也可以通过点一次id加载查询出来出来子部门&#xff0c;我们用一次拿到说有json数据加载出来 数据不多可以用递归&#xff0c;数据很多就用懒加载的方式 由于子部门比较深就不适合&#xff0c;权…...

【Terraform学习】使用 Terraform 从 EC2 实例访问 S3 存储桶(Terraform-AWS最佳实战学习)

使用 Terraform 从 EC2 实例访问 S3 存储桶 实验步骤 前提条件 安装 Terraform&#xff1a; 地址 下载仓库代码模版 本实验代码位于 task_ec2_s3connet 文件夹中。 变量文件 variables.tf 在上面的代码中&#xff0c;您将声明&#xff0c;aws_access_key&#xff0c;aws_…...

ZDRE6VP4-1X/50MG24K4V比例压力阀放大器

DRE 6-11/100MG24K4M比、DRE 10-6X/200YMG24K4M、DRE 20-52/200YMG24K4M、DRE 20-6X/200YMG24K4M、ZDRE6VP1-1X/315MG24N9K4M、ZDRE6VP4-1X/50MG24K4V、Z3DRE6VP2-2X/50G24K4M、Z3DRE6VP1-2X/100G24K4M、Z3DRE10VP2-1X/100XYG24K4M、Z3DRE10VP1-1X/315XLG24K4V 功能: 设定值通…...

纠缠辅助的量子网络:原理、技术、发展与挑战

7月11日&#xff0c;中国科大网络空间安全学院和陆军院士工作室李忠辉博士为第一作者、薛开平教授为通讯作者的量子网络综述论文“Entanglement-Assisted Quantum Networks: Mechanics, Enabling Technologies, Challenges, and Research Directions”在通信领域知名期刊《IEEE…...

React Native 可触摸组件基础知识

在 React Native 中要实现可触摸的组件方式有三种&#xff0c;第一种方式就是使用TouchableHighlight组件&#xff0c;第二种方式就是使用TouchableOpacity组件&#xff0c;最后一种方式就是使用TouchableWithoutFeedback组件。 TouchableHighlight TouchableHighlight组件主…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...