单链表算法 - 链表的回文结构

链表的回文结构_牛客题霸_牛客网对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为。题目来自【牛客题霸】icon-default.png?t=N7T8https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa思路1:

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {int left = 0;int right = 0;// write code here//创建数组int count = 0;//创建数组int arr[900];ListNode* ptail = A;//将链表中的数据插入到数组里面以及计算链表的个数while(A){arr[count++] = A->val;A = A->next;}//下标是从0开始的right = count-1;//比较是否为回文结构while(left++ < right--){if(arr[left] != arr[right]){return false;}}return true;}
};

提交结果:

在代码中我们申请了900个整型的数组,因为我们知道链表最大是900个节点,这里的空间复杂度也是O(1),复合要求,那如果这里没有对链表节点个数进行限制,这种思路肯定是不行的。

除此之外,该思路只能在牛客上通过,若换成力扣,通过不了,因为如果明确规定空间复杂度为O(1)的话就不能额外的去申请空间,更别说申请900个整型了,牛客平台对时间和空间复杂度没有力扣那么严格。

思路2:

代码: 

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*///C++和C在这里唯一的区别就是不需要再typedef
//typedef struct ListNode ListNode; - 不用class PalindromeList {
public:
ListNode* reveres(ListNode* A)
{ListNode* prev = NULL;ListNode* ptail = A;ListNode* next = A->next;while(ptail){ptail->next = prev;prev = ptail;ptail = next;next = next->next;}return prev;
}bool chkPalindrome(ListNode* A) {// write code here//找中间节点ListNode* fast = A;ListNode* slow = A;while(slow && slow->next){fast = fast->next;slow = slow->next->next;}//fast就是中间节点ListNode* right =  reveres(fast);//逆置并返回逆置后的第一个节点ListNode* left = A;while(right){if(right->val != left->val){return false;}right = right->next;left = left->next;}return true;}
};

提交结果:

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

字节面试:如何让单机下Netty支持百万长连接?

最近有同学在面试遇到了一道非常有深度的面试题&#xff1a; 如何让单机下Netty支持百万长连接&#xff1f; 当时在群里问小北&#xff0c;我发现我也没有系统化的梳理过这个问题&#xff0c;所以一时也没有回答的特别好。 痛定思痛的我赶紧去各种搜集资料&#xff0c;系统化的…

unity渲染人物模型透明度问题

问题1&#xff1a;有独立的手和衣服的模型&#xff0c;但最终只渲染出来半透明衣服 问题2&#xff1a;透明度贴图是正确的但显示却不正确 这上面两个模型的问题都是因为人物模型是一个完整的&#xff0c;为啥有些地方可以正常显示&#xff0c;有些地方透明度却有问题。 其中…

数据结构小测试:排序算法

目录 1、请简述数据结构八大排序算法的思路。 2、常用排序算法手写 冒泡排序&#xff1a; 选择排序&#xff1a; 快速排序&#xff1a; 归并排序&#xff1a; 堆排序&#xff1a; 3、额外再加一个二分查找吧 1、请简述数据结构八大排序算法的思路。 冒泡排序&#xff…

亚信安全发布2024年第24期《勒索家族和勒索事件监控报告》

本周态势快速感知 本周&#xff0c;勒索软件LockBit涉嫌对美国一家生产乙烯基产品的公司&#xff08;Homeland Vinyl&#xff09;进行攻击。LockBit声称他们已窃取了销售、库存、财务交易数据及其他公司记录&#xff0c;并声明将于2024年7月19日公开这些被盗信息。本周全球共监…

【iOS】OC类与对象的本质分析

目录 前言clang常用命令对象本质探索属性的本质对象的内存大小isa 指针探究 前言 OC 代码的底层实现都是 C/C代码&#xff0c;OC 的对象都是基于 C/C 的数据结构实现的&#xff0c;实际 OC 对象的本质就是结构体&#xff0c;那到底是一个怎样的结构体呢&#xff1f; clang常用…

AI算法17-贝叶斯岭回归算法Bayesian Ridge Regression | BRR

贝叶斯岭回归算法简介 贝叶斯岭回归&#xff08;Bayesian Ridge Regression&#xff09;是一种回归分析方法&#xff0c;它结合了岭回归&#xff08;Ridge Regression&#xff09;的正则化特性和贝叶斯统计的推断能力。这种方法在处理具有大量特征的数据集时特别有用&#xff…

安全入门day01

一、常用名词 1、前后端 &#xff08;1&#xff09;前端 前端主要负责用户界面的展示和交互。它通常包括HTML、CSS和JavaScript等技术的使用&#xff0c;也可能使用各种前端框架和库&#xff0c;如React、Vue.js、Angular等&#xff0c;来构建更加复杂和动态的用户界面。前端…

校验el-table中表单项

需求&#xff1a; 表格中每一行都有几个必填项&#xff0c;如用户提交时有未填的选项&#xff0c;将该选项标红且给出提示&#xff0c;类似el-form 的那种校验 el-table本身并没有校验的方法&#xff0c;而且每一行的输入框也是通过插槽来实现的&#xff0c;因此我们要自己跟…

log4js node日志插件

最近不是特别忙在用express搭建后台项目&#xff0c;在开发过程中遇到了需要输入日志的问 本来想直接用node自带的console来实现&#xff0c;后来发现console输出的日志达不到自己希望的 日志格式&#xff0c;后来各种百度发现了log4js插件&#xff0c;本文来记录log4js插件使用…

一文-深入了解Ansible常见模块、安装和部署

1 Ansible 介绍 Ansible是一个配置管理系统configuration management system, python 语言是运维人员必须会的语言, ansible 是一个基于python 开发的&#xff08;集合了众多运维工具 puppet、cfengine、chef、func、fabric的优点&#xff09;自动化运维工具, 其功能实现基于ss…

django实现用户的注册、登录、注销功能

创建django项目的步骤&#xff1a;Django项目的创建步骤-CSDN博客 一、前置工作 配置数据库&#xff0c;设置数据库引擎为mysql 1、在settings文件中找到DATABASES, 配置以下内容 DATABASES {"default": {ENGINE: django.db.backends.mysql, # 数据库引擎NAME: dja…

基于springboot和mybatis的RealWorld后端项目实战二之实现tag接口

修改pom.xml 新增tag数据表 SET FOREIGN_KEY_CHECKS0;-- ---------------------------- -- Table structure for tags -- ---------------------------- DROP TABLE IF EXISTS tags; CREATE TABLE tags (id bigint(20) NOT NULL AUTO_INCREMENT,name varchar(255) NOT NULL,PR…

【hadoop大数据集群 2】

【hadoop大数据集群 2】 文章目录 【hadoop大数据集群 2】1. 虚拟机克隆2. 时间同步3. 环境变量配置、启动集群、关闭集群 1. 虚拟机克隆 克隆之后一定要重新生成新虚拟机唯一的MAC地址和UUID等&#xff0c;确保新虚拟机与源虚拟机在网络拓扑中不发生冲突。 注意1.生成新的MA…

IDEA关联数据库

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

Spring Boot2(Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递)

目录 一、Spring Boot 的Web开发 1. 静态资源映射规则 2. enjoy模板引擎 二、springMVC 1. springMVC-请求处理 测试&#xff1a; 以post方式请求 限制请求携带的参数 GetMapping 查询 PostMapping 新增 DeleteMapping删除 PutMapping 修改 2. springMVC-参…

电子画册制作攻略:如何让你的作品吸引眼球

随着数字化时代的到来&#xff0c;电子画册作为一种新兴的传播媒介&#xff0c;已经越来越受到人们的青睐。它不仅能够以生动的形式展现内容&#xff0c;还可以轻松地实现互动和分享。然而&#xff0c;如何让你的电子画册作品在众多竞争中脱颖而出&#xff0c;吸引更多眼球呢&a…

景联文科技构建高质量心理学系知识图谱,助力大模型成为心理学科专家

心理大模型正处于快速发展阶段&#xff0c;在临床应用、教育、研究等多个领域展现出巨大潜力。 心理学系知识图谱能够丰富心理大模型的认知能力&#xff0c;使其在处理心理学相关问题时更加精确、可靠和有洞察力。这对于提高心理健康服务的质量和效率、促进科学研究以及优化教育…

【MySQL进阶篇】SQL优化

1、插入数据 insert优化 批量插入&#xff1a; insert into tb_user values(1,tom),(2,cat),(3,jerry); 如果插入数据过大&#xff0c;可以将业务分割为多条insert语句进行插入。 手动提交事务&#xff1a; start transaction; insert into tb_user values(1,tom),(2,cat),(3…

Linux——多路复用之select

目录 前言 一、select的认识 二、select的接口 三、select的使用 四、select的优缺点 前言 在前面&#xff0c;我们学习了五种IO模型&#xff0c;对IO有了基本的认识&#xff0c;知道了select效率很高&#xff0c;可以等待多个文件描述符&#xff0c;那他是如何等待的呢&a…

视频活码如何在线制作?分享快速制作二维码的方法

视频想要快速的分享现在有很多的人会选择二维码的方式&#xff0c;将视频转换成二维码通过手机扫码就能够快速在线查看视频内容&#xff0c;这样可以不占用扫码者自身的内存&#xff0c;随时扫码从云端调取内容查看&#xff0c;更加的方便快捷便于内容的分享。那么具体该如何实…