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

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...