单链表算法实战：解锁数据结构核心谜题——链表的回文结构
题目如下：
解题过程如下：
回文结构举例：
回文数字：12521、12321、1221……
回文字符串：“abcba”、“abba”……
并不是所有的循环嵌套的时间复杂度都是O(n^2)
可以用C++写C程序：
C++里可以直接使用ListNode作为结构体类型名：
思路1：新建一个单链表，保存原来链表的结点，反转新链表，遍历这两个链表比较结点是否相同。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//新建一个单链表，保存原链表的结点，反转新链表ListNode* n1, *n2, *n3;n1 = NULL, n2 = A, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}//遍历这两个链表，比较这两个链表中的结点数值是否相等while (A && n1){if (A->val == n1->val){A = A->next;n1 = n1->next;}else {return false;}}return true;}
};
思路2：创建一个数组（大小900），遍历原链表将结点中的数值依次存储在数组中，判断数组是否为回文结构。
创建一个数组，有900个空间，空间复杂度：O(900) == O(1)
i表示存储的结点中数据的个数（数组中有效数据的个数）
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//新建一个数组（大小900）int arr[900] = { 0 };//遍历单链表，将链表结点中的数值依次存储在数组中ListNode* pcur = A;int i = 0;while (pcur){arr[i++] = pcur->val;pcur = pcur->next;}//判断数组是否是回文结构int left = 0, right = i - 1;while (left < right){if (arr[left] != arr[right]){return false;}left++;right--;}return true;}
};
题干没有“保证链表长度小于等于900”这句话，思路2不适用。
思路3：找到链表的中间结点（快慢指针），中间结点作为新链表的头结点然后反转链表，比较两个链表里的值是否相等。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//找到链表的中间结点(快慢指针)ListNode* slow, *fast;slow = fast = A;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}//中间结点作为新链表的头结点，反转新链表ListNode* n1, *n2, *n3;n1 = NULL, n2 = slow, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}//比较两个链表中的结点存储的数值ListNode* newHead = n1;ListNode* head = A;while (newHead && head){if (newHead->val != head->val){return false;}head = head->next;newHead = newHead->next;}return true;}
};
思路3代码完善：找链表的中间结点和反转链表可以分别封装成一个函数实现。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:ListNode* middleNode(ListNode* head){ListNode* slow, *fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* head){if (head == NULL){return NULL;}ListNode* n1, *n2, *n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;}bool chkPalindrome(ListNode* A) {//1.找到链表的中间结点ListNode* mid = middleNode(A);//2.中间结点作为头结点，反转链表ListNode* right = reverseList(mid);//3.比较两个链表的结点里的值是否相等ListNode* left = A;while (right){if (left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};
相关文章：
单链表算法实战：解锁数据结构核心谜题——链表的回文结构
题目如下： 解题过程如下： 回文结构举例： 回文数字：12521、12321、1221…… 回文字符串：“abcba”、“abba”…… 并不是所有的循环嵌套的时间复杂度都是O(n^2) 可以用C写C程序： C里可以直接使用ListNode…...
【2024年 CSDN博客之星】我的2024年创作之旅：从C语言到人工智能，个人成长与突破的全景回顾
我的2024年创作之旅：从C语言到人工智能，个人成长与突破的全景回顾 引言 回望2024年，我不仅收获了技术上的成长，更收获了来自CSDN平台上无数粉丝、朋友以及网友们的支持与鼓励。在这条创作之路上，CSDN不仅是我展示技术成…...
Qt Enter和HoverEnter事件
介绍 做PC开发的过程中或多或少都会接触到鼠标的悬停事件，Qt中处理鼠标悬停有Enter和HoverEnter两种事件 相同点 QEvent::Enter对应QEnterEvent，描述的是鼠标进入控件坐标范围之内的行为，QEnterEvent可以抓取鼠标的位置；QEvent…...
Python：元组构造式和字典推导式
（Python 元组构造式和字典推导式整理笔记） 1. 元组构造式 1.1 创建元组 使用圆括号： tuple1 (1, 2.5, (three, four), [True, 5], False) print(tuple1) # 输出: (1, 2.5, (three, four), [True, 5], False) 省略圆括号： tup…...
科普篇 | “机架、塔式、刀片”三类服务器对比
一、引言 在互联网的世界里，服务器就像是默默运转的超级大脑，支撑着我们日常使用的各种网络服务。今天，咱们来聊聊服务器家族中的三位 “明星成员”：机架式服务器、塔式服务器和刀片式服务器。如果把互联网比作一座庞大的城市&…...
数据结构——概念与时间空间复杂度
目录 前言 一相关概念 1什么是数据结构 2什么是算法 二算法效率 1如何衡量算法效率的好坏 2算法的复杂度 三时间复杂度 1时间复杂度表示 2计算时间复杂度 2.1题一 2.2题二 2.3题三 2.4题四 2.5题五 2.6题六 2.7题七 2.8题八 四空间复杂度 1题一 2题二 3…...
centos7 配置国内镜像源安装 docker
使用国内镜像源：由于 Docker 的官方源在国内访问可能不稳定，你可以使用国内的镜像源，如阿里云的镜像源。手动创建 /etc/yum.repos.d/docker-ce.repo 文件，并添加以下内容： [docker-ce-stable] nameDocker CE Stable -…...
PyCharm配置Python环境
1、打开PyCharm项目 可以从File-->Open-->选择你的项目路径-->OK，或者直接点击Open，找到项目路径-->OK，如图所示(点击Ok后可能有下面的弹窗，选择“Trust Project”即可，然后选择“New Window”打开项目) …...
 系统安装jenkins服务)
Linux（Centos、Ubuntu) 系统安装jenkins服务
该文章手把手演示在Linux系统下如何安装jenkins服务、并自定义jenkins数据文件位置、以及jenkins如何设置国内镜像源加速，解决插件下载失败问题 安装方式：war包安装 阿里云提供的war下载源地址：https://mirrors.aliyun.com/jenkins/war/?s…...
语义检索(1))
本地大模型编程实战(02)语义检索(1)
文章目录 准备加载文档分割文档嵌入矢量存储查询矢量库检索返回评分先嵌入查询文本再检索 检索器总结代码 我们在百度、必应、谷歌等搜索引擎中使用的检索都是基于字符串的：用户输入字符串后，搜索引擎先对搜索内容进行分词，然后在已经进行了倒…...
使用 Redis 实现分布式锁的基本思路
使用 Redis 实现分布式锁的基本思路 在分布式系统中，多个进程或服务可能会同时访问共享资源（如数据库、缓存、文件等），这可能会导致数据不一致或并发冲突。Redis 由于其高性能和单线程模型，是实现分布式锁的一个常见选…...
SQL-leetcode—1193. 每月交易 I
1193. 每月交易 I 表：Transactions ---------------------- | Column Name | Type | ---------------------- | id | int | | country | varchar | | state | enum | | amount | int | | trans_date | date | ---------------------- id 是这个表的主键。 该表包含…...
【MYSQL】mysql 常用命令
文章目录 1. 数据库管理命令2. 表管理命令3. 数据操作命令4. 数据查询进阶5. 用户与权限管理6. 使用脚本操作数据库 1. 数据库管理命令 -- 查看所有数据库 SHOW DATABASES;-- 创建数据库 CREATE DATABASE 数据库名;-- 选择数据库 USE 数据库名;-- 删除数据库 DROP DATABASE 数…...
linux 内核学习方向以及职位
### 学习路径 1. 基础阶段： - C语言高级特性 - 指针和内存管理 - 数据结构实现 - 位操作 - 多线程编程 - Linux系统编程 - 文件I/O操作 - 进程管理 - 信号处理 - IPC机制 - Socket编程 - 必备知识 - 操作系统原理 - 计算机体系结构 - …...
DeepSeek火爆，参数量、激活参数 和 预训练 token 量 是什么？
最近DeepSeek火爆，爆出了几个关键参数，分别是参数量、激活参数 和 预训练 token 量。 这里用通俗的语言给大家解释一下~ 首先要知道1B 是 Billion（十亿）的缩写 参数量：671B（6710 亿） 想象你…...
设计新的 Kibana 仪表板布局以支持可折叠部分等
作者：来自 Elastic Teresa Alvarez Soler, Hannah Mudge 及 Nathaniel Reese 在 Kibana 中构建可折叠仪表板部分需要彻底改造嵌入式系统并创建自定义布局引擎。这些更新改进了状态管理、层次结构和性能，同时为新的高级仪表板功能奠定了基础。 我们正在开…...
vscode如何安装vue语法支持
在VSCode中安装Vue语法支持非常简单。1、你需要安装“Vetur”扩展，这是一个专门为Vue.js开发设计的扩展；2、你可以通过VSCode的扩展市场轻松找到并安装它；3、安装完成后，你还可以根据需要进行一些配置，以优化你的开发体…...
从零安装 LLaMA-Factory 微调 Qwen 大模型成功及所有的坑
文章目录 从零安装 LLaMA-Factory 微调 Qwen 大模型成功及所有的坑一 参考二 安装三 启动准备大模型文件 四 数据集（关键）！4.1 Alapaca格式4.2 sharegpt4.3 在 dataset_info.json 中注册4.4 官方 alpaca_zh_demo 例子 999条数据, 本机微调 5分…...
(read)-示例及核心部件)
easyexcel-导入(读取)(read)-示例及核心部件
文章目录 导入(读取)(read)-示例及核心部件导入(读取)(read)-核心部件EasyExcel(EasyExcelFactory) # 入口read() # read()方法用于构建workbook(工作簿)对象，new ExcelReaderBuilder()doReadAll()这里选XlsxSaxAnalyser这个实现类吧然后到这个类XlsxRowHandler&…...
10 Hyperledger Fabric 介绍
简介 HypeLedger（超级账本）是由Linux基金会2015年创建的首个面向企业应用场景的开源分布式账本平台。 HypeLedger Fabric是HypeLedger种的区块链项目之一HypeLedger Fabric引入权限管理在架构设计上支持可插拔、可扩展是首个面向联盟链场景的开源项目 …...
第28章 测试驱动开发模式：深入绿条模式及相关技术
写在前面 这本书是我们老板推荐过的，我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后，我突然思考，对于测试开发工程师来说，什么才更有价值呢？如何让 AI 工具更好地辅助自己写代码，或许…...
PTMD2.0-疾病相关的翻译后修饰数据库
翻译后修饰（PTMs，post-translational modifications）通过调节蛋白质功能参与了几乎所有的生物学过程，而 PTMs 的异常状态常常与人类疾病相关。在此，PTMD 2.0展示与疾病相关的 PTMs 综合数据库，其中包含 93 …...
gradle生命周期钩子函数
文章目录 0. 总结表格1. 构建初始阶段gradle.settingsEvaluated()gradle.projectsLoaded() 2. 配置阶段gradle.beforeProject()gradle.afterProject()gradle.projectEvaluated()gradle.afterEvaluate()gradle.taskGraph.whenReady 3. 执行阶段gradle.taskGraph.beforeTaskgradl…...
解读整理——内核初始化(main init)之内存的划分)
操作系统(Linux Kernel 0.11Linux Kernel 0.12)解读整理——内核初始化(main init)之内存的划分
前言 MMU：内存管理单元(Memory Management Unit)完成的工作就是虚拟地址到物理地址的转换，可以让系统中的多个程序跑在自己独立的虚拟地址空间中，相互不会影响。程序可以对底层的物理内存一无所知，物理地址可以是不连续的&#x…...
WPF基础 | WPF 布局系统深度剖析：从 Grid 到 StackPanel
WPF基础 | WPF 布局系统深度剖析：从 Grid 到 StackPanel 一、前言二、Grid 布局：万能的布局王者2.1 Grid 布局基础：构建网格世界2.2 子元素定位与跨行列：布局的精细操控2.3 自适应布局：灵活应变的秘诀 三、StackPanel…...
C++红黑树详解
文章目录 红黑树概念规则为什么最长路径不超过最短路径的二倍？红黑树的时间复杂度红黑树的结构插入叔叔节点情况的讨论只变色(叔叔存在且为红)抽象的情况变色单旋（叔叔不存在或叔叔存在且为黑）变色双旋（叔叔不存在或叔叔存在且为黑…...
【经验分享】ARM Linux-RT内核实时系统性能评估工具
【经验分享】ARM Linux-RT内核实时系统性能评估工具 前言下载和编译方法常用工具介绍总结 前言 最近在研究Linux-RT实时系统，介绍下常用的实时系统的性能评估工具。 下载和编译方法 用git下载 git clone git://git.kernel.org/pub/scm/utils/rt-tests/rt-tests.…...
【kong gateway】5分钟快速上手kong gateway
kong gateway的请求响应示意图 安装 下载对应的docker 镜像 可以直接使用docker pull命令拉取，也可以从以下地址下载：kong gateway 3.9.0.0 docker 镜像 https://download.csdn.net/download/zhangshenglu1/90307400， postgres-13.tar http…...
Vue入门(Vue基本语法、axios、组件、事件分发）
Vue入门 Vue概述 Vue (读音/vju/，类似于view)是一套用于构建用户界面的渐进式框架，发布于2014年2月。与其它大型框架不同的是，Vue被设计为可以自底向上逐层应用。Vue的核心库只关注视图层，不仅易于上手，还便于与第三…...
【可实战】Linux 系统扫盲、 Shell扫盲（如何写一个简单的shell脚本）
一、Linux系统扫盲 1.Linux 能运行主要的 UNIX 工具软件、应用程序和网络协议 2.Linux 的发行版说简单点就是将 Linux 内核与应用软件做一个打包。 目前市面上较知名的发行版有：Ubuntu、RedHat、CentOS、Debian、Fedora、SuSE、OpenSUSE、Arch Linux、SolusOS 等…...
【深入理解SpringCloud微服务】Sentinel源码解析——DegradeSlot熔断规则
Sentinel源码解析——DegradeSlot熔断规则 断路器原理复习DegradeSlot熔断规则原理源码解析DegradeSlot#entry()DegradeSlot#exit(Context, ...)ResponseTimeCircuitBreakerExceptionCircuitBreaker 断路器原理复习 断路器一般有三个状态：关闭、打开、半开…...
电脑系统bcd文件损坏修复方法：小白也会的修复方法
电脑系统bcd文件损坏怎么办?当电脑开机时出现bcd文件损坏，一般情况是由于电脑系统的引导坏了，需要进行修复。现在越来越多的小伙伴遇到电脑引导丢失或者安装后无法正常引导的问题，我们现在一般是pe下进行修复引导，那么电脑系统bc…...
链式存储结构
不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。 结点 结点由数据域、指针域组成。 头结点、头指针和首元结点 头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过…...
Oracle 创建用户和表空间
Oracle 创建用户和表空间 使用sys 账户登录 建立临时表空间 --建立临时表空间 CREATE TEMPORARY TABLESPACE TEMP_POS --创建名为TEMP_POS的临时表空间 TEMPFILE /oracle/oradata/POS/TEMP_POS.DBF -- 临时文件 SIZE 50M -- 其初始大小为50M AUTOEXTEND ON -- 支持…...
媒体新闻发稿要求有哪些？什么类型的稿件更好通过？
为了保证推送信息的内容质量，大型新闻媒体的审稿要求一向较为严格。尤其在商业推广的过程中，不少企业的宣传稿很难发布在这些大型新闻媒体平台上。 媒体新闻发稿要求有哪些？就让我们来了解下哪几类稿件更容易过审。 一、媒体新闻发稿要求有哪…...
Qt中QVariant的使用
1.使用QVariant实现不同类型数据的相加 方法：通过type函数返回数值的类型，然后通过setValue来构造一个QVariant类型的返回值。 函数： QVariant mainPage::dataPlus(QVariant a, QVariant b) {QVariant ret;if ((a.type() QVariant::Int) &a…...
)
3.4 Go函数作用域(标识符)
作用域标识符 简单来说，作用域指的是标识符可以起作用的范围，即其可见范围。将标识符的可见性限制在一定范围内，这个范围就是作用域。 把标识符约束在一定的可见范围内，这个范围就是作用域。 1. 宇宙块 特点：预定义…...
搭建Spring Boot开发环境
JDK（1.8及以上版本） Apache Maven 3.6.0 修改settings.xml 设置本地仓库位置 <localRepository>D:/repository</localRepository> 设置远程仓库镜像 <mirror><id>alimaven</id><name>aliyun maven</name&…...
洛谷 P5709：Apples Prologue / 苹果和虫子
【题目来源】 https://www.luogu.com.cn/problem/P5709 【题目描述】 小 B 喜欢吃苹果。她现在有 m（1≤m≤100）个苹果，吃完一个苹果需要花费 t（0≤t≤100）分钟，吃完一个后立刻开始吃下一个。现在时间过去了…...
PyTorch张量操作reshape view permute transpose
1. reshape() 和 view() view和reshape都用于改变张量的shape view是reshape的一个特例，view要求张量在内存中是连续的，否则会抛出错误，view只能用于contiguous的张量 reshape会自动处理contiguous的情况，如果张量是contiguous…...
JAVAweb学习日记（八） 请数据库模型MySQL
一、MySQL数据模型 二、SQL语言 三、DDL 详细见SQL学习日记内容 四、DQL-条件查询 五、DQL-分组查询 聚合函数： 分组查询： 六、DQL-分组查询 七、分页查询 八、多表设计-一对多&一对一&多对多 一对多-外键： 一对一： 多…...
【ElasticSearch】 Java API Client 7.17文档
本文章内容根据 Elastic Search Java API Client 7.17 版本官方文档 内容翻译而来，用于方便后续学习翻阅 序言 这是适用于 Elasticsearch 的官方 Java API Client 文档。该客户端针对所有 Elasticsearch API 提供强类型的请求和响应。 功能 所有 Elasticsearc…...
Python “字典” 实战案例：5个项目开发实例
Python “字典” 实战案例：5个项目开发实例 内容摘要 本文包括 5 个使用 Python 字典的综合应用实例。具体是： 电影推荐系统配置文件解析器选票统计与排序电话黄页管理系统缓存系统（LRU 缓存） 以上每一个实例均有完整的程序代…...
Qt中Widget及其子类的相对位置移动
Qt中Widget及其子类的相对位置移动 最后更新日期：2025.01.25 下面让我们开始今天的主题… 一、开启篇 提出问题：请看上图，我们想要实现的效果是控件黄色的Widge（m_infobarWidget）t随着可视化窗口（m_glWidge…...
4.flask-SQLAlchemy，表Model定义、增删查改操作
介绍 SQLAlchemy是对数据库的一个抽象 开发者不用直接与SQL语句打交道 Python对象来操作数据库 SQLAlchemy是一个关系型数据库 安装 flask中SQLAlchemy的配置 from flask import Flask from demo.user_oper import userdef create_app():app Flask(__name__)# 使用sessi…...
字节跳动自研HTTP开源框架Hertz简介附使用示例
字节跳动自研 HTTP 框架 Hertz Hertz 是字节跳动自研的高性能 HTTP 框架，专为高并发、低延迟的场景设计。它基于 Go 语言开发，结合了字节跳动在微服务架构中的实践经验，旨在提供更高效的 HTTP 服务开发体验。 1. 背景介绍 随着字节跳动业务…...
Effective C++ 规则51：编写 new 和 delete 时需固守常规
1、背景 在 C 中，如果你需要为类自定义 new 和 delete，必须遵循一些约定和规则，以确保内存管理的一致性、可维护性和安全性。当我们使用 new 和 delete 操作时，C 编译器会： 调用全局或类特定的 operator new 来分配内…...
[RoarCTF 2019]Easy Calc1
题目 查看页面源代码 <script>$(#calc).submit(function(){$.ajax({url:"calc.php?num"encodeURIComponent($("#content").val()),type:GET,success:function(data){$("#result").html(<div class"alert alert-success">…...
【Bug 记录】el-sub-menu 第一次进入默认不高亮
项目场景： 项目场景：el-sub-menu 第一次进入默认不高亮 问题描述 例如：sub-menu 的 index 后端默认传过来是 number，我们需要手动转为 string，否则会有警告，而且第一次进入 sub-menu 默认不高亮。 解决方…...
自然语言处理——从原理、经典模型到应用
1. 概述 自然语言处理（Natural Language Processing，NLP）是一门借助计算机技术研究人类语言的科学，是人工智能领域的一个分支，旨在让计算机理解、生成和处理人类语言。其核心任务是将非结构化的自然语言转换为机器可以…...