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

【LeetCode】234. 回文链表

回文链表

题目描述:

        给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

示例 1:

输入:head = [1,2,2,1]
输出:true

示例 2:

输入:head = [1,2]
输出:false

提示:

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

方法一思路分析:

反转链表的一半

  1. 使用快慢指针找到链表的中点:快指针每次移动两步,慢指针每次移动一步,当快指针到达链表末尾时,慢指针就位于链表的中点(对于奇数个节点的链表,慢指针位于中间两个节点的第一个)。

  2. 反转链表的后半部分:从慢指针开始,反转链表的后半部分。

  3. 比较前后两部分:将反转后的后半部分与原始链表的前半部分进行比较,如果每个节点都相等,则是回文链表。

代码实现:

public class Solution {  public boolean isPalindrome(ListNode head) {  // 如果链表为空或只有一个节点,直接返回true  if (head == null || head.next == null) {  return true;  }  // 使用快慢指针找到链表的中点  ListNode slow = head;  ListNode fast = head;  ListNode prev = null;  while (fast != null && fast.next != null) {  prev = slow;  slow = slow.next;  fast = fast.next.next;  }  // 如果链表长度为奇数,则跳过中点  if (fast != null) {  slow = slow.next;  }  // 反转链表的后半部分  ListNode secondHalfHead = reverseList(slow);  // 比较前半部分和反转后的后半部分  ListNode p1 = head;  ListNode p2 = secondHalfHead;  while (p2 != null) {  if (p1.val != p2.val) {  return false;  }  p1 = p1.next;  p2 = p2.next;  }  return true;  }  // 反转链表的方法  private ListNode reverseList(ListNode head) {  ListNode prev = null;  ListNode curr = head;  while (curr != null) {  ListNode nextTemp = curr.next;  curr.next = prev;  prev = curr;  curr = nextTemp;  }  return prev;  }  
}

方法二思路分析:使用栈

        遍历链表,将遍历到的每个节点的值压入栈中。然后,再次遍历链表,同时从栈中弹出元素,比较从链表中取出的元素和从栈中弹出的元素是否相等。如果所有元素都匹配,则链表是回文的。

public class Solution {  public boolean isPalindrome(ListNode head) {  Stack<Integer> stack = new Stack<>();  ListNode curr = head;  // 遍历链表,将值压入栈  while (curr != null) {  stack.push(curr.val);  curr = curr.next;  }  // 再次遍历链表,同时从栈中弹出元素进行比较  curr = head;  while (curr != null) {  if (curr.val != stack.pop()) {  return false;  }  curr = curr.next;  }  return true;  }  
}

方法三思路分析:使用数组

        遍历链表,将遍历到的每个节点的值存储在一个数组中。然后,使用双指针技术(一个从头开始,一个从尾开始)来比较数组中的元素。这种方法的空间复杂度是O(n),其中n是链表的长度。

public class Solution {  public boolean isPalindrome(ListNode head) {  List<Integer> vals = new ArrayList<>();  ListNode curr = head;  // 遍历链表,将值存储在数组中  while (curr != null) {  vals.add(curr.val);  curr = curr.next;  }  // 使用双指针比较数组中的元素  int i = 0, j = vals.size() - 1;  while (i < j) {  if (!vals.get(i).equals(vals.get(j))) {  return false;  }  i++;  j--;  }  return true;  }  
}

相关文章:

【LeetCode】234. 回文链表

回文链表 题目描述&#xff1a; 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#…...

零基础学会机器学习,到底要多久?

这两天啊&#xff0c;有不少朋友和我说&#xff0c;想学机器学习&#xff0c;但是之前没有基础&#xff0c;不知道能不能学得会。 首先说结论&#xff0c;只要坚持&#xff0c;就能学会&#xff0c;但是一定不能三天打鱼两天晒网&#xff0c;要持之以恒&#xff0c;至少每隔两…...

视频汇聚/安防监控综合平台EasyCVR接入海康私有协议EHOME显示失败是什么原因?

安防监控/视频综合管理平台/视频集中存储/磁盘阵列EasyCVR视频汇聚平台&#xff0c;支持多种视频格式和编码方式&#xff08;H.264/H.265&#xff09;&#xff0c;能够轻松对接各类前端监控设备&#xff0c;实现视频流的统一接入与集中管理。安防监控EasyCVR平台支持多种流媒体…...

Qt解析XML

背景 本来想解析VS的项目配置文件(*.vcxproj)&#xff0c;配合cppclean来发现多余的#incldue。 结果发现低估了难度&#xff0c;VS会间接引入许多目录。 略有不甘&#xff0c;暂且作为一个解析XML文件的示例。 代码 VSProjectParser.h #include <QVector> #include…...

PwnLab: init-文件包含、shell反弹、提权--靶机渗透思路讲解

Vulnhub靶机链接回【PwnLab】 首页有一个登录框 image-20240807124822770 他没有验证码&#xff0c;我们试试暴力破解 image-20240807122743025 开始爆破了&#xff0c;全部失败&#xff0c;哈哈哈 image-20240807122851001 nmap全端口扫描试试 image-20240807131408315 有…...

OpenCV—二值化Threshold()、adaptiveThreshold()

cv2.threshold() c&#xff1a;double cv::threshold ( InputArray src, OutputArray dst, double thresh, double maxval, int type ) (注&#xff1a;源图片, 目标图, 阈值, 填充色, 阈值类型) python:cv.threshold(src,thresh, maxval, type[, dst]) src&#xff1a;源图片…...

第二天:java面向对象编程(OOP)

第二天&#xff1a;java面向对象编程&#xff08;OOP&#xff09; 1. 深入理解OOP四大特性 封装&#xff08;Encapsulation&#xff09;&#xff1a;学习如何将数据&#xff08;属性&#xff09;和操作数据的方法&#xff08;行为&#xff09;组合成一个独立的单元&#xff0…...

Selenium + Python 自动化测试07(滑块的操作方法)

我们的目标是&#xff1a;按照这一套资料学习下来&#xff0c;大家可以独立完成自动化测试的任务。 本篇文章主要讲述如何操作滑块。 目前很多系统登录或者注册的页面都有滑块相关的验证&#xff0c;selenium 中对滑块的基本操作采用了元素的拖曳的方式。需要用到Actiochains模…...

三防平板满足多样化定制为工业领域打造硬件解决方案

在当今工业领域&#xff0c;数字化、智能化的发展趋势日益显著&#xff0c;对于高效、可靠且适应各种复杂环境的硬件设备需求不断增长。三防平板作为一种具有坚固耐用、防水防尘防摔特性的工业级设备&#xff0c;正以其出色的性能和多样化的定制能力&#xff0c;为不同行业的应…...

pytorch,用lenet5识别cifar10数据集(训练+测试+单张图片识别)

目录 LeNet-5 LeNet-5 结构 CIFAR-10 pytorch实现 lenet模型 训练模型 1.导入数据 2.训练模型 3.测试模型 测试单张图片 代码 运行结果 LeNet-5 LeNet-5 是由 Yann LeCun 等人在 1998 年提出的一种经典卷积神经网络&#xff08;CNN&#xff09;模型&#xff0c;主要…...

Word卡顿的处理方法

1. 检查和关闭后台程序 关闭不必要的后台程序,释放系统资源。使用任务管理器(Ctrl + Shift + Esc)查看占用CPU和内存较高的应用,并关闭它们。2. 更新Microsoft Office 确保你的Microsoft Office软件是最新版本。新版本通常修复了已知的性能问题。打开Word,点击文件 > 账…...

在 Linux上常见的10大压缩格式解压命令和它们对应的压缩格式

文章目录 前言一、解压 .zip 文件二、解压 .tar.gz 或 .tgz 文件三、解压 .tar 文件四、解压 .tar.bz2 文件五、解压 .tar.xz 文件六、解压 .gz 文件七、解压 .bz2 文件八、解压 .xz 文件九、解压 .7z 文件十、解压 .rar 文件总结 前言 Linux 命令可以解压不同格式的压缩文件。…...

【数据结构】三、栈和队列:6.链队列、双端队列、队列的应用(树的层次遍历、广度优先BFS、先来先服务FCFS)

文章目录 2.链队列2.1初始化&#xff08;带头结点&#xff09;不带头结点 2.2入队&#xff08;带头结点&#xff09;2.3出队&#xff08;带头结点&#xff09;❗2.4链队列c实例 3.双端队列考点:输出序列合法性栈双端队列 队列的应用1.树的层次遍历2.图的广度优先遍历3.操作系统…...

技术速递|使用 Native Library Interop 为 .NET MAUI 创建绑定

作者&#xff1a;Rachel Kang 排版&#xff1a;Alan Wang 在当今的应用开发领域&#xff0c;通过利用本机功能来扩展 .NET 应用程序的能力非常宝贵。.NET MAUI 处理程序架构使开发人员能够使用 .NET 代码直接操作本机控件&#xff0c;甚至允许无缝创建跨平台自定义控件。然而&a…...

Linux笔记 --- 标准IO

系统IO的最大特点一个是更具通用性&#xff0c;不管是普通文件、管道文件、设备节点文件、接字文件等等都可以使用&#xff0c;另一个是他的简约性&#xff0c;对文件内数据的读写在任何情况下都是带任何格式的&#xff0c;而且数据的读写也都没有经过任何缓冲处理&#xff0c;…...

洛谷:B3625 迷宫寻路

迷宫寻路 题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个 n m n\times m nm 矩阵&#xff0c;每个位置要么是空地&#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置&#xff0c;问能否…...

【C#】explicit、implicit与operator

字面解释 explicit&#xff1a;清楚明白的;易于理解的;(说话)清晰的&#xff0c;明确的;直言的;坦率的;直截了当的;不隐晦的;不含糊的。 implicit&#xff1a;含蓄的;不直接言明的;成为一部分的;内含的;完全的;无疑问的。 operator&#xff1a;操作人员;技工;电话员;接线员;…...

Vue:Vuex-Store使用指南

一、简介 1.1Vuex 是什么 Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。Vuex 也集成到 Vue 的官方调试工具 devtools extension (opens new window)&#xf…...

对经典动态规划问题【爬台阶】的一些思考

背景 今天在做Leetcode题目时&#xff0c;做到了一道经典的动态规划问题&#xff1a;爬楼梯&#xff0c;题目的大致意思很简单&#xff0c;有个小孩正在上楼梯&#xff0c;楼梯有n阶台阶&#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法&#xff0c;计算小孩有多少种上…...

开发一个能打造虚拟带货直播间的工具!

在当今数字化时代&#xff0c;直播带货已成为电商领域的一股强劲力量&#xff0c;其直观、互动性强的特点极大地提升了消费者的购物体验。 然而&#xff0c;随着技术的不断进步&#xff0c;传统直播带货模式正逐步向更加智能化、虚拟化的方向演进&#xff0c;本文将深入探讨如…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

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.…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...