【算法】判断一个链表是否为回文结构
问:
给定一个单链表的头节点head,请判断该链表是否为回文结构
例:
1 -> 2 -> 1返回true;1 -> 2 -> 2 -> 1返回true;15 -> 6 -> 15返回true
答:
笔试:初始化一个栈用来存放链表中右半部分的元素(快慢指针),弹栈的顺序是链表的逆序
public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}
}
//额外空间n
public static boolean isPalindrome1 (Node head) {if (head == null || head.next == null) {return true;}Stack<Node> satck = new Stack<Node>();//为栈赋值做准备Node cur = head;//将链表的数据赋到栈中while (cur != null) {stack.push(cur);cur = cur.next;}//比较栈中的数据与链表中的数据while (head != null) {if (head.value != stack.pop().value) {return false;}head = head.next;}return true;
}
//额外空间n/2,快慢指针
public static boolean isPalindrome2 (Node head) {if (head == null || head.next == null) {return true;}Node slow = head.next;Node fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}Stack<Node> stack = new Stack<Node>();//把后半段链表赋值到栈中while (slow != null) {stack.push(slow);slow = slow.next;}//将弹栈元素与前半段链表中元素对比while (!stack.isEmpty()) {if (head.value != stack.pop().value) {return false;}head = head.next;}return true;
}
面试:快慢指针找到终点位置,把右半个链表逆序,中点指向null,p1、p2分别为从左端、右端出发的指针,二者不断进行比对,最后恢复原来的结构




//额外空间1
public static boolean isPalindrome3 (Node head) {if (head == null || head.next == null) {return true;}//找到链表中点Node slow = head;Node fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}//反转链表的后半段fast = slow.next;slow.next = null;Node n = null;while (fast != null) {n = fast.next;fast.next = slow;slow = fast;fast = n;}//将前半段与后半段比较n = slow;fast = head;boolean res = true;while (slow != null && fast != null) {if (slow.value != fast.value) {res = false;break;}slow = slow.next;fast = fast.next;}//把链表恢复原样slow = n.next;n.next = null;while (slow != null) {fast = slow.next;slow.next = n;n = slow;slow = fast;}return res;
}相关文章:
【算法】判断一个链表是否为回文结构
问: 给定一个单链表的头节点head,请判断该链表是否为回文结构 例: 1 -> 2 -> 1返回true;1 -> 2 -> 2 -> 1返回true;15 -> 6 -> 15返回true 答: 笔试:初始化一个栈用来…...
计算机网络之---ICMP协议与Ping命令
ICMP 协议 ICMP (Internet Control Message Protocol) 是一种网络层协议,主要用于在 IP 网络中传递控制消息。ICMP 主要用于网络设备之间的故障报告和诊断,帮助设备检测网络连接问题。它是 IP 协议的核心部分之一,用于发送错误消息和操作信息…...
【硬件介绍】Type-C接口详解
一、Type-C接口概述 Type-C接口特点:以其独特的扁头设计和无需区分正反两面的便捷性而广受欢迎。这种设计大大提高了用户的使用体验,避免了传统USB接口需要多次尝试才能正确插入的问题。Type-C接口内部结构:内部上下两排引脚的设计虽然可能不…...
【Pandas】pandas Series rtruediv
Pandas2.2 Series Binary operator functions 方法描述Series.add()用于对两个 Series 进行逐元素加法运算Series.sub()用于对两个 Series 进行逐元素减法运算Series.mul()用于对两个 Series 进行逐元素乘法运算Series.div()用于对两个 Series 进行逐元素除法运算Series.true…...
项目开发版本控制Git流程规范
个人&测试&预发布&生产分支命名 1)个人分支: 从sit或者master进行切出,姓名切出分支命名,或者日期切出分支命名 示例:liuys_sit、20250110_sit2)测试分支: sit3)用户验…...
STM32 : 波特率发生器
波特率发生器 1. 发送器和接收器的波特率 波特率寄存器 (BRR): 在串行通信中,发送器和接收器的波特率是由波特率寄存器(BRR)中的一个值 DIV 来确定的。 2. 计算公式 计算公式: 详细解释 1. 波特率寄存器 (BRR) BRR: 波特率寄存器是一…...
STM32 USB组合设备 MSC CDC
STM32 USB组合设备 MSC CDC实现 教程 教程请看大佬niu_88 手把手教你使用USB的CDCMSC复合设备(基于stm32f407) 大佬的教程很好,很详细,我调出来了,代码请见我绑定的资源 注意事项 值得注意的是: 1、 cu…...
继续以“实用”指导Pythonic编码(re通配表达式)(2024年终总结2)
弃现成工具手剥任务🧐,我哈哈滴就像笨笨的傻大个儿😋。 (笔记模板由python脚本于2025年01月12日 23:29:33创建,本篇笔记适合熟悉正则表达式的coder翻阅) 【学习的细节是欢悦的历程】 Python官网:https://www.python.or…...
Flutter使用BorderRadiusTween实现由矩形变成圆形的动画
BorderRadiusTween 是插值动画中,用于组件边框半径的类,专门作用于组件边框和半径动化过度。 这个类继承自Tween,用法相似。 下面是示例写法 class BorderRadiusTweenPage extends StatefulWidget {overrideState<StatefulWidget> c…...
VSCode 中的 launch.json 配置使用
VSCode 中的 launch.json 配置使用 在 VSCode 中,launch.json 文件用于配置调试设置,特别是用来定义如何启动和调试你的应用。它允许你配置不同的调试模式、运行参数和调试选项。 基本结构 launch.json 文件位于 .vscode 文件夹内,可以通过…...
深度学习张量的秩、轴和形状
深度学习张量的秩、轴和形状 秩、轴和形状是在深度学习中我们最关心的张量属性。 秩轴形状 秩、轴和形状是在深度学习中开始使用张量时我们最关心的三个属性。这些概念相互建立,从秩开始,然后是轴,最后构建到形状,所以请注意这…...
Redis有哪些常用应用场景?
大家好,我是锋哥。今天分享关于【Redis有哪些常用应用场景?】面试题。希望对大家有帮助; Redis有哪些常用应用场景? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Redis 是一个高性能的开源键值对(Key-Va…...
vue3+ts+element-plus 输入框el-input设置背景颜色
普通情况: 组件内容: <el-input v-model"applyBasicInfo.outerApplyId"/> 样式设置: ::v-deep .el-input__wrapper {background-color: pink; }// 也可以这样设置 ::v-deep(.el-input__wrapper) {background-color: pink…...
Ubuntu 磁盘修复
Ubuntu 磁盘修复 在 ubuntu 文件系统变成只读模式,该处理呢? 文件系统内部的错误,如索引错误、元数据损坏等,也可能导致系统进入只读状态。磁盘坏道或硬件故障也可能引发文件系统只读的问题。/etc/fstab配置错误,可能…...
使用RSyslog将Nginx Access Log写入Kafka
个人博客地址:使用RSyslog将Nginx Access Log写入Kafka | 一张假钞的真实世界 环境说明 CentOS Linux release 7.3.1611kafka_2.12-0.10.2.2nginx/1.12.2rsyslog-8.24.0-34.el7.x86_64.rpm 创建测试Topic $ ./kafka-topics.sh --zookeeper 192.168.72.25:2181/k…...
通过Apache、Nginx限制直接访问public下的静态文件
一、Apache 在public目录下的.htaccess文件中添加如下规则,来拒绝除了指定文件类型之外的所有请求 <FilesMatch "\.(?!(jpg|jpeg|png|gif|css|js|ico)$)[^.]$">Order Allow,DenyDeny from all </FilesMatch> 上述配置表示仅允许访问.jpg …...
uniapp小程序中隐藏顶部导航栏和指定某页面去掉顶部导航栏小程序
uniappvue3开发小程序过程中隐藏顶部导航栏和指定某页面去掉顶部导航栏方法 在page.json中 "globalStyle": {"navigationStyle":"custom",}, 如果是指定某个页面关闭顶部导航栏,在style中添加"navigationStyle": "cus…...
Agile Scrum 敏捷开发方法
Agile Scrum 是一种敏捷开发方法,广泛用于软件开发以及其他项目管理领域。它强调迭代式的工作流程、团队协作、灵活应对变化和持续改进,旨在通过快速交付和反馈来最大化项目价值。Scrum 是 Agile(敏捷)方法中的一种具体实践框架&a…...
【算法与数据结构】—— 回文问题
回文问题 目录 1、简介2、经典的回文问题(1) 判断一个字符串是否为回文(2) 给定字符集求构建的最长回文长度(3) 求最长回文子串方法一:中心拓展方法二:Manacher 算法 (4) 求回文子串的数目方法一:中心拓展方法二:Manacher 算法 1、…...
用vscode写latex-1
一般大伙使用 LaTeX 大体有两种方案, 一种是在本地配置环境或使用本地的软件,如 vscode LaTeX,texlive,lyx 等等; 另一种是线上 LaTeX 平台,其中用的最多的是 Overleaf,还有一部分高校也有自…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
