当前位置: 首页 > 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;本文将深入探讨如…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...