闯关leetcode——234. Palindrome Linked List
大纲
- 题目
- 地址
- 内容
- 解题
- 代码地址
题目
地址
https://leetcode.com/problems/palindrome-linked-list/description/
内容
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
解题
这题就是要检测一个链表是否符合回文结构。一种比较简单的思路就是使用栈来将链表内容反序,然后逐项对比。但是这个方案不符合O(1) space的要求,因为辅助计算的栈中数据大小会随着链表中数据量增大而增大。
回文数的结构是中间对称。虽然使用栈来处理可以避免对“中间”的寻找,但是O(1) space限制了我们对栈的使用。这就促使我们要来寻找“中间”。一种简单的办法就是使用不同速度的指针向后探寻——一个一次向后移动一个元素,一个一次向后移动两个元素。这样快的那个指针会先到链表末尾,而慢的那个指针则会找到“中间”附近的位置。
为什么是“中间”附近的位置呢?因为链表的元素数量可能是奇数,也可能是偶数。如下图所示,如果是奇数,慢指针将指向“中间”的前一个元素;如果是偶数,慢指针指向的是回文左半边的最后一个元素。

不管慢指针指向的是哪种情况,我们都已让其下一个元素(含)之后的所有元素反转,然后从链表头部开始对比。只要一个链表遍历结束后,仍然没有出现不同值的元素,则可以认为是回文数。

struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr || head->next == nullptr) return true;ListNode* slow = head;ListNode* fast = head->next;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}ListNode* pre = nullptr;ListNode* cur = slow->next;slow->next = nullptr;while (cur != nullptr) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}while (head != nullptr && pre != nullptr) {if (head->val != pre->val) return false;head = head->next;pre = pre->next;}return true;}
};

代码地址
https://github.com/f304646673/leetcode/blob/main/234-Palindrome-Linked-List/cplusplus/src/solution.hpp
相关文章:
闯关leetcode——234. Palindrome Linked List
大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/palindrome-linked-list/description/ 内容 Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Example 1: Input: head [1,2,2,1] Output: tru…...
通过源码分析类加载器里面可以加载的类
类列表 每一个ClassLoader里面的类列表,类的数量都是固定的。 对上一节中的dex反编译 使用DexClassLoader类动态加载插件dex 利用jadx对dex进行反编译可以看到有哪些类 源码分析 BaseDexClassLoader 从BaseDexClassLoader类加载器开始分析 在BaseDexClassLoade…...
RSA算法:数字安全的基石
## RSA算法:数字安全的基石 RSA算法是现代密码学的重要组成部分,它为安全通信和数据保护提供了坚实的基础。本文将探讨RSA算法的基本原理、实施过程以及实际应用场景。 ### 一、RSA算法概述 RSA(Rivest-Shamir-Adleman)算法是由…...
DPDK高性能处理框架VPP
VPP 环境安装 $ git clone -b stable/1801 https://github.com/FDio/vpp.git $ ./extras/vagrant/build.sh && make 在编译成功以后,会生成上图红色的 deb 表 $ dpkg –i vpp-lib_18.01.2-1~g9b554f3_amd64.deb $ dpkg –i vpp_18.01.2-1~g9b554f3_amd…...
Spring工厂方式实现实例化bean有哪些方式?
在Spring框架中,实例化Bean的方式有多种,其中通过工厂方法(Factory Method)来创建Bean是一种常见的方式。这种方式允许你通过自定义的工厂类或静态方法来生成Bean实例,从而提供了更灵活和复杂的实例化逻辑。 以下是Sp…...
衡石分析平台系统分析人员手册-指标分析看板
指标分析看板为业务指标量身打造的分析看板。拖拽指标就可形成看板,通过点选对指标分析图表进行配置,整个过程简单易上手。分析人员根据业务分析场景制作图表,无需对指标的数据进行再次加工处理。 指标分析是为业务指标定制的看板࿰…...
《C++17 结构化绑定:解锁不同类型处理的秘籍》
在 C17 中,结构化绑定是一个强大且引人注目的特性。它为开发者处理复杂的数据结构和多种类型的返回值提供了一种简洁而高效的方式。然而,正确处理不同类型的绑定和初始化问题是充分发挥这一特性优势的关键。 理解结构化绑定的本质 结构化绑定允许我们使…...
大型音频模型:AudioLLMs
大型音频模型(Large Audio Models,简称AudioLLMs)是近年来人工智能领域的一个重要研究方向,它们基于深度学习和大模型架构,能够处理和理解复杂的音频数据。以下是对大型音频模型的研究综述: 1. 引言 随着…...
【ShuQiHere】️理解Python中的相对路径:使用 `..` 和 `.` 的指南
【ShuQiHere】️🌟 目录 引言什么是相对路径?路径中使用 . 和 ..相对路径的示例使用子文件夹中的数据使用相对路径的最佳实践结论进一步探索 引言 🌍 在Python编程中,处理文件时了解如何使用相对路径至关重要。相对路径使我们…...
DMFLDR数据载入使用实践
1、DMFLDR概述 1.1DMFLDR功能介绍 dmfldr(DM Fast Loader)是 DM 提供的快速数据装载命令行工具。用户通过使用 dmfldr 工具能够把按照一定格式 排序的文本数据以简单、快速、高效的方式载入到 DM 数据库中,或把 DM 数据库中的数据按照一定格…...
发布 NPM 包时,终端显示发布成功但实际上版本并没有更新,可能是由于以下原因
如果发布仍然没有生效,可以检查以下几点: 版本号是否更新: 如果版本号没有更新,NPM 会拒绝发布新的包版本。运行以下命令以确保版本号增加了: bash 复制代码 npm version patch # 更新小版本号 正确的 NPM 注册表&a…...
Java学习Day57:碧水金睛兽!(Spring Cloud微服务1.0)
1.微服务入门 (1).单体架构与分布式架构 单体架构: 将业务的所有功能集中在一个项目中开发,打成一个包部署优点: 架构简单、部署成本低 ; 缺点: 耦合度高项目打包部署到Tomcat,用户直接访问。用户量增加后…...
物联网开发教程专栏介绍与专栏说明——列表目录查阅(持续更新)
阿齐Archie《物联网开发:完整实现单片机通信模组云服务器智能应用软件》专栏 为方便查阅学习本专栏,特整理专栏介绍与专栏说明 一、专栏介绍 物联网开发教程专栏目前有P1和P2系列,P1系列为《手把手完整实现STM32ESP8266MQTT阿里云APP应用》…...
uni-app实现app展示进度条在线更新以及定时更新提醒
需求:需要在app启动后进行检查更新,如果有更新就提示更新,可以点击确定更新或者暂时不更新,如果不更新,就将当前的时间进行缓存,并且再次进入时进行对比,只要超过一天时间就继续提醒检查更新 第…...
【Linux】进程间通信(命名管道、共享内存、消息队列、信号量)
作者主页: 作者主页 本篇博客专栏:Linux 创作时间 :2024年11月2日 命名管道: 如果我们想在不相关的进程之间交换数据,可以使用FIFO文件来做这项工作,它经常被称为命名管道。命名管道是一种特殊类型的文…...
[Android]从FLAG_SECURE禁止截屏看surface
在应用中,设置activity的flag为FLAG_SECURE就可以禁止截屏,截屏出来是黑色的, 试验一下, 注意事项 影响: 设置 FLAG_SECURE 标志后,用户将无法对该Activity进行截屏或录制屏幕。这个标志会影响所有屏幕录…...
python 五子棋小游戏
1. 实现效果 Python五子棋小游戏 2. 游戏规则 规则说明,五子棋人机对战游戏规则如下: Ⅰ 默认规则 - 五子棋规则 对局双方:各执一色棋子,一方持黑色棋子,另一方持白色棋子。棋盘与开局:空棋盘开局…...
JeecgBoot集成工作流实战教程
Activiti是一个轻量级的工作流程和业务流程管理(BPM)平台,它主要面向业务人员、开发人员和系统管理员。这个平台的核心是一个快速且可靠的Java BPMN 2流程引擎。Activiti是开源的,并且基于Apache许可证进行分发。它可以运行在任何…...
第三十章 章节练习商品列表组件封装
目录 一、需求说明 二、技术要点 三、完整代码 3.1. main.js 3.2. App.vue 3.3. MyTable.vue 3.4. MyTag.vue 一、需求说明 1. my-tag 标签组件封装 (1) 双击显示输入框,输入框获取焦点 (2) 失去焦点,隐藏输入框 (3) 回显标签信息 (4) 内…...
NumPy 高级索引
NumPy 高级索引 NumPy 是 Python 中用于科学计算的核心库之一,它提供了一个强大的N维数组对象和许多用于操作这些数组的函数。在 NumPy 中,除了基本的索引和切片操作外,还提供了高级索引功能,这使得您可以以更加灵活和高效的方式访问和操作数组中的数据。本文将详细介绍 N…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
