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

算法系列-力扣234-回文链表判定

回文链表判定

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

方法一:栈反转对比法

解题思路:找到中间节点后用栈辅助反转对比
解题方法:
找到链表的中间节点并判断奇数还是偶数
头结点到中间节点前的节点入栈,偶数从中间节点开始和栈内元素进行比较;
奇数从中间节点后面的节点开始和栈内元素进行比较;
若比较到最后一个节点都相等该链表为回文链表(栈空或比较到最后一个节点)
时间复杂度:O(n)
空间复杂度:O(n)

import java.util.List;
import java.util.Stack;import javax.management.ListenerNotFoundException;/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public static boolean isPalindrome(ListNode head) {/*** head -> 1 -> 2 -> 2 -> 1 -> null* head -> 1 -> 2 -> 1 -> null* 找到链表的中间节点并判断奇数还是偶数* 头结点到中间节点的节点入栈,偶数从中间节点开始和栈内元素进行比较;* 奇数从中间节点后面的节点开始和栈内元素进行比较;* 若比较到最后一个节点都相当该链表为回文链表(栈空或比较到最后一个节点)*/if(head == null){return false;}ListNode dummy = new ListNode(-1);dummy.next=head;ListNode slow=dummy;ListNode fast=dummy;ListNode midNode=null;Boolean isEvent=true;while (fast.next!=null){slow=slow.next;if(fast.next.next!=null) {fast = fast.next.next;} else{fast=fast.next;isEvent=false;}}midNode = isEvent ? slow.next : slow;Stack<ListNode> stack=new Stack<>();ListNode p=dummy.next;while(p!=midNode){stack.push(p);p=p.next;}ListNode m=isEvent?midNode:midNode.next;while(m!=null){ListNode tmp=stack.pop();if(m.val!=tmp.val){return false;}m=m.next;}return true;}
}

方法二:链自反转对比法

解题思路:找到中间节点后用栈辅助反转对比
解题方法:
找到链表的中间节点并判断奇数还是偶数
继续利用双指针反转中间节点前的链表。
偶数从中间节点开始和反转链进行比较;
奇数从中间节点后面的节点开始和反转链进行比较;
若比较到最后一个节点都相等该链表为回文链表(栈空或比较到最后一个节点)
时间复杂度:O(n)
空间复杂度:O(1)

   public static boolean isPalindrome(ListNode head) {/*** [1,0,1]* head -> 1 -> 2 -> 2 -> 1 -> null* head -> 1 -> 2 -> 1 -> null找到链表的中间节点并判断奇数还是偶数继续利用头插法反转中间节点前的链表。偶数从中间节点开始和反转链进行比较;奇数从中间节点后面的节点开始和反转链进行比较;若比较到最后一个节点都相等该链表为回文链表(栈空或比较到最后一个节点)*/if(head == null){return false;}ListNode dummy = new ListNode(-1);dummy.next=head;ListNode slow=dummy;ListNode fast=dummy;ListNode midNode=null;Boolean isEvent=true;while (fast.next!=null){slow=slow.next;if(fast.next.next!=null) {fast = fast.next.next;} else{fast=fast.next;isEvent=false;}}midNode = isEvent ? slow.next : slow;ListNode p = head;head=null;while (p!=midNode){ListNode tmp=p.next;p.next=head;head=p;p=tmp;}//偶数从中间节点开始和反转链进行比较ListNode m = isEvent ? midNode : midNode.next;boolean isPalindrome=true;p=head;while (isPalindrome && p!=null){if(p.val!=m.val){isPalindrome=false;}p=p.next;m=m.next;}// 还原链表p = head;head=midNode;while (p!=null){ListNode tmp=p.next;p.next=head;head=p;p=tmp;}return  isPalindrome;}

相关文章:

算法系列-力扣234-回文链表判定

回文链表判定 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 方法一&#xff1a;栈反转对比法 解题思路&#xff1a;找到中间节点后用栈辅助反转对比 解题方法&#xff1…...

算法通关村——海量数据场景下的热门算法题的处理方法

1. 从40个亿中产生一个不存在的整数 题目要求&#xff1a;给定一个输入文件&#xff0c;包含40亿个非负整数&#xff0c;请设计一个算法&#xff0c;产生一个不存在该文件中的整数&#xff0c;假设你有1GB的内存来完成这项任务。 ● 进阶&#xff1a;如果只有10MB的内存可用&a…...

【C++从0到王者】第二十五站:多继承的虚表

文章目录 前言一、多继承的虚函数表二、菱形继承与菱形虚拟继承的虚函数表1.菱形继承2.菱形虚拟继承的虚函数表 三、抽象类1.抽象类的概念2.接口继承与实现继承 总结 前言 其实关于单继承的虚函数表我们在上一篇文章中已经说过了&#xff0c;就是派生类中的虚表相当于拷贝了一…...

老程序员教你如何笑对问题,轻松培养逻辑思考和解决问题的能力

原文链接 ​​​​​​​老程序员教你如何笑对问题&#xff0c;轻松培养逻辑思考和解决问题的能力 故事发生在一个阳光明媚的午后&#xff0c;我们的主人公&#xff0c;老李&#xff0c;一位拥有十年工作经验的 Python 老程序员&#xff0c;正悠哉地在喝着咖啡。 这时&#x…...

Omni Recover for Mac(专业的iPhone数据恢复软件)

Omni Recover for Mac是一款专业的Mac数据恢复软件&#xff0c;能够帮助用户快速找回被误删除、格式化、病毒攻击等原因造成的文件和数据&#xff0c;包括图片、视频、音频、文档、邮件、应用程序等。同时&#xff0c;Omni Recover for Mac还具有数据备份和清理功能&#xff0c…...

视频垂直镜像播放,为您的影片带来新鲜感

大家好&#xff01;在制作视频时&#xff0c;我们常常希望能够给观众带来一些新鲜感和独特的视觉效果。而垂直镜像播放是一个能够让您的影片与众不同的技巧。然而&#xff0c;传统的视频剪辑软件往往无法直接实现视频的垂直镜像播放&#xff0c;给我们带来了一些困扰。现在&…...

十一、MySQL(DQL)聚合函数

1、聚合函数 注意&#xff1a;在使用聚合函数时&#xff0c;所有的NULL是不参与运算的。 2、实际操作&#xff1a; &#xff08;1&#xff09;初始化表格 &#xff08;2&#xff09;统计该列数据的个数 基础语法&#xff1a; select count(字段名) from 表名; &#xff1b;统…...

C语言:三子棋小游戏

简介&#xff1a; 目标很简单&#xff1a;实现一个 三子棋小游戏。三子棋大家都玩过&#xff0c;规则就不提及了。本博文中实现的三子棋在对局中&#xff0c;电脑落子是随机的&#xff0c;不具有智能性&#xff0c;玩家的落子位置使用键盘输入坐标。下面开始详细介绍如何实现一…...

JAVA - PO DTO 生成器

PO DTO 生成器 假设你是一个Java 高级程序员&#xff0c;我会提供一些信息&#xff0c;你需要帮我自动生成Java的PO、DTO 对象。 这些信息有着固定的形式&#xff0c;第一行是对象的类名&#xff0c;其后的每一行都是该对象的属性(简称“属性”)。 对于我属性&#xff0c;格式…...

tcpdump

TCPDump是一个用于抓取网络数据包的命令行工具。它可以帮助网络管理员和开发人员分析网络流量、故障排除以及安全问题。下面是一些TCPDump的详细用法&#xff1a; 基本用法&#xff1a; 监听指定网络接口&#xff1a;tcpdump -i eth0通过IP地址过滤&#xff1a;tcpdump host 19…...

数据通信——传输层TCP(可靠传输原理的ARQ)

引言 上一篇讲述了停止等待协议的工作流程&#xff0c;在最后提到了ARQ自动请求重传机制。接下来&#xff0c;我们就接着上一篇的篇幅&#xff0c;讲一下ARQ这个机制 还是这个图来镇楼 ARQ是什么&#xff1f; 发送端对出错的数据帧进行重传是自动进行的&#xff0c;因而这种…...

Compose - 交互组合项

按钮 Button OutLinedButton带外边框、TextButton只是文字、IconButton只是图标形状。 Button(onClick { }, //点击回调modifier Modifier,enabled true, //启用或禁用interactionSource MutableInteractionSource(),elevation ButtonDefaults.elevatedButtonElevation( /…...

【发版公告】Virbox Protector 3.1.3.19051 发版- elf 文件支持导入表保护

深盾安全-软件保护工具 Virbox Protector 3 &#xff08; 3.1.3.19051&#xff09;迎来了版本升级.本次升级支持了 elf 文件导入表保护。 以下是本次 Virbox Protector 发版的主要功能&#xff1a; 新功能 1. ELF格式的程序支持导入表保护(Beta)&#xff1b;&#xff1b; 2…...

点云数据做简单的平面的分割 三维场景中有平面,杯子,和其他物体 实现欧式聚类提取 对三维点云组成的场景进行分割

点云分割是根据空间,几何和纹理等特征对点云进行划分,使得同一划分内的点云拥有相似的特征,点云的有效分割往往是许多应用的前提,例如逆向工作,CAD领域对零件的不同扫描表面进行分割,然后才能更好的进行空洞修复曲面重建,特征描述和提取,进而进行基于3D内容的检索,组合…...

C++之std::search应用实例(一百八十九)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…...

一文详解 requests 库中 json 参数和 data 参数的用法

在requests库当中&#xff0c;requests请求方法&#xff0c;当发送post/put/delete等带有请求体的请求时&#xff0c;有json和data2个参数可选。 众所周知&#xff0c;http请求的请求体格式主要有以下4种&#xff1a; application/json applicaiton/x-www-from-urlencoded mu…...

Django学习笔记-AcApp端授权AcWing一键登录

笔记内容转载自 AcWing 的 Django 框架课讲义&#xff0c;课程链接&#xff1a;AcWing Django 框架课。 AcApp 端使用 AcWing 一键授权登录的流程与之前网页端的流程一样&#xff0c;只有申请授权码这一步有一点细微的差别&#xff1a; 我们在打开 AcApp 应用之后会自动向 AcW…...

如何在小红书进行学习直播

诸神缄默不语-个人CSDN博文目录 因为我是从B站开始的&#xff0c;所以一些直播常识型的东西请见我之前写的如何在B站进行学习直播这一篇。 本篇主要介绍一些小红书之与B站不同之处。 小红书在手机端是可以直接点击“”选择直播的。 文章目录 1. 电脑直播-小红书直播软件2. 电…...

F5服务器负载均衡能力如何?一文了解

但凡知道服务器负载均衡这个名词的&#xff0c;基本都知道 F5&#xff0c;因为负载均衡是 F5 的代表作&#xff0c;换句话来说&#xff0c;负载均衡就是由 F5 发明的。提到F5服务器负载均衡能力如何&#xff1f;不得不关注F5提出的关于安全、网络全面优化的解决方案&#xff0c…...

Ubuntu18.04安装docker-io

1. 安装docker 1.1 网上一搜&#xff0c;全是更新仓库、下载依赖、添加docker的gpg密钥、添加docker仓库、安装docker-ce的步骤&#xff0c;但是在安装docker-ce时却提示“package "docker-ce" has no installation candidate”&#xff0c;就很迷。 1.2 安装docke…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...