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

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...

渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用

阻止除自定义标签之外的所有标签 先输入一些标签测试&#xff0c;说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时&#xff08;如通过点击或键盘导航&…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...

SpringCloud优势

目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...