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

【题解】 判断一个链表是否为回文结构

判断一个链表是否为回文结构

题目链接:判断一个链表是否为回文结构

解题思路1:借助数组

遍历链表将值都放在数组中,再遍历数组元素,判断该数组是否为一个回文结构

代码如下:

    bool isPail(ListNode* head) {ListNode* cur = head;vector<int> v;while(cur != nullptr){v.push_back(cur->val);cur = cur->next;}for(int i=0,j=v.size()-1; i<j; ++i,--j){if(v[i] != v[j]){return false;}}return true;}

解题思路2:反转部分链表进行对比

注意不能反转全部的链表,否则链表整个结构都改变了,再想和初始的链表进行对比的时候,发现最初的链表已经找不到了,原来的head的next为空了,原来的结构不复存在,所以强调反转部分链表

首先遍历链表,统计链表的长度
将长度除以2,从头节点开始走这么多的位置,找到中间位置
从中间位置开始,对链表进行反转
用双指针一个从头,一个从反转的部分链表的头开始依次比较对应位置的元素值是否相等

代码如下:

    ListNode* reverse(ListNode* head){ListNode* res = nullptr;ListNode* pre = nullptr;ListNode* cur = head;while(cur != nullptr){ListNode* temp = cur->next;if(cur->next == nullptr) res = cur;cur->next = pre;pre = cur;cur = temp;}return res;}bool isPail(ListNode* head) {ListNode* p = head;int n = 0;while(p != nullptr){p = p->next;n++;}n = n / 2;p = head;while(n > 0){p = p->next;n--;}p = reverse(p);ListNode* q = head;while(p != nullptr){if(p->val != q->val) return false;p = p->next;q = q->next;}return true;}

解题思路3:利用快慢指针找中点

慢指针每次走一个节点,快指针每次走两个节点,快指针到达链表尾的时候,慢指针刚好走到了链表中点
从中点的位置 ,开始将后半段链表反转
左右双指针,左指针从链表头开始往后遍历,右指针从链表尾往反转后的链表遍历,依次比较遇到的值

代码如下:

    ListNode* reverse(ListNode* head){ListNode* res = nullptr;ListNode* pre = nullptr;ListNode* cur = head;while(cur != nullptr){ListNode* temp = cur->next;if(cur->next == nullptr) res = cur;cur->next = pre;pre = cur;cur = temp;}return res;}bool isPail(ListNode* head) {ListNode* slow = head;ListNode* fast = head;//双指针找中点while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;}//中点处反转slow = reverse(slow);fast = head;while(slow != nullptr){if(slow->val != fast->val) return false;fast = fast->next;slow = slow->next;} return true;}

解题思路4:栈逆序

将元素放到栈中,再依次取出栈顶元素和链表进行对比,如果都相同,那该链表就是回文链表

    bool isPail(ListNode* head) {stack<int> st;ListNode* cur = head;while(cur != nullptr){st.push(cur->val);cur = cur->next;}cur = head;while(!st.empty()){if(cur->val != st.top()) return false;st.pop();cur = cur->next;}return true;}

相关文章:

【题解】 判断一个链表是否为回文结构

判断一个链表是否为回文结构 题目链接&#xff1a;判断一个链表是否为回文结构 解题思路1&#xff1a;借助数组 遍历链表将值都放在数组中&#xff0c;再遍历数组元素&#xff0c;判断该数组是否为一个回文结构 代码如下&#xff1a; bool isPail(ListNode* head) {ListNod…...

Microsoft Message Queuing Denial-of-Service Vulnerability

近期官方公布了一个MSMQ的拒绝服务漏洞&#xff0c;可能因为网络安全设备的更新&#xff0c;影响业务&#xff0c;值得大家关注。 漏洞具体描述参见如下&#xff1a; Name: Microsoft Message Queuing Denial-of-Service Vulnerability Description: Microsoft Message Queuing…...

软件设计师(五)软件工程基础知识

一、软件工程概述 软件开发和维护过程中所遇到的各种问题称为“软件危机”。 软件工程是指应用计算机科学、数学及管理科学等原理&#xff0c;以工程化的原则和方法来解决软件问题的工程&#xff0c;其目的是提高软件生产率、提高软件质量、降低软件成本。 #mermaid-svg-h3j6K…...

Java中的JUnit单元测试方法的使用

Java中的JUnit单元测试方法 使用步骤如下&#xff1a; 选中当前工程 - 右键选择&#xff1a;build path - add libraries - JUnit 4 - 下一步创建Java类&#xff0c;进行单元测试。 此时的Java类要求&#xff1a;① 此类是public的 ②此类提供公共的无参的构造器此类中声明单…...

一文学透设计模式——抽象工厂模式

创建者模式 抽象工厂模式 概念 抽象工厂模式是围绕一个超级工厂创建其他工厂。该超级工厂又称为其他工厂的工厂。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。 这是很多地方对于抽象工厂模式的描述&#xff0c;说实话感觉不是特别好懂。…...

Vue3与Vue2区别和总结(1)

在2020年9月18日&#xff0c;Vue.js发布3.0版本&#xff0c;代号&#xff1a;One Piece&#xff08;海贼王&#xff09; 既然vue2已经存在了六七年之久为什么还要研发vue3呢&#xff1f; 那就不得不提vue3带来的提升了 1.Vue3带来了什么 1.性能的提升 打包大小减少41% 初次…...

【华秋推荐】物联网入门学习模块 ESP8266

随着全球信息技术的不断进步和普及&#xff0c;物联网成为当今备受关注的技术热点之一。通过物理和数字设备之间的连接来实现自动化和互联互通的网络。无线传感器、云计算和大数据分析等技术&#xff0c;物联网使设备能够相互交流和共享信息&#xff0c;实现智能化的自动化操作…...

本科专科毕业论文如何选题-附1000多论文题目-论文选题--【毕业论文】

文章目录 本系列校训毕设的技术铺垫论文选题选题目的和意义&#xff1a;选题举例参考文献 配套资源 本系列校训 互相伤害互相卷&#xff0c;玩命学习要你管&#xff0c;天生我才必有用&#xff0c;我命由我不由天&#xff01; 毕业论文不怕难&#xff0c;毕业设计来铺垫&#…...

pip安装jupyter notebook

之前电脑安装了anaconda&#xff0c;里面安装了jupyter notebook&#xff0c;用来做PPT之类的展示总让我觉得有点“炫酷”。 现在换了新电脑。没有anaconda&#xff0c;纯粹只是装了python3.11&#xff0c;然后突然也想手工安装下jupyter notebook&#xff0c;于是只能通过pip方…...

STM32刷Micropython固件参考指南

STM32刷Micropython固件指南 其实刷固件和普通的程序下载烧录无多大的差异&#xff0c;主要是其他因数的影响导致刷固件或刷完固件无法运行的情况和相关问题。 &#x1f4d1;刷固件教程 固件下载。目前所支持的stm32型号有这些&#xff1a; stm32f0, stm32f4, stm32f7, stm32g…...

学生信息管理系统自动化测试

项目地址&#xff1a; http://82.156.151.156:8080/login.html 一、系统测试用例 二、测试实现过程 先是根据自己的项目设计了一个 UI 自动化测试用例, 然后根据这个测试用例使用了 selenium4自动化测试工具和 JUnit5单元测试框架结合实现的 web 自动化测试.。 测试模块划分…...

Java面向对象之toString()方法

toString()方法 toString()方法在Object类中定义&#xff0c;其返回值是String类型&#xff0c;返回类名和它的引用地址。在进行String与其它类型数据的连接操作时&#xff0c;自动调用toString()方法。 Date nownew Date(); System.out.println(“now”now); 相当于 System.…...

MySQL(一)

mysql简介 1、什么是数据库 &#xff1f; 数据库&#xff08;Database&#xff09;是按照数据结构来组织、存储和管理数据的仓库&#xff0c;它产生于距今六十多年前&#xff0c;随着信息技术和市场的发展&#xff0c;特别是二十世纪九十年代以后&#xff0c;数据管理不再仅仅…...

使用docker部署node和react应用

使用docker部署node和react应用 Docker 使开发人员能够将所有应用程序打包到容器中。这些容器可以在任何安装了 Docker 的机器上运行&#xff0c;并且应用程序将是相同的。这是在多个系统上运行代码库克隆的好方法&#xff0c;并且我们可以确保它们都是相同的。 在本文中&…...

对List集合、数组去重

前言&#xff1a; 还记得在2021我发布的第一篇博客就是关于数组的去重&#xff0c;从那一刻开始&#xff0c;命运的齿轮开始转动…… 扯远了哈哈哈&#xff0c;我重新写这篇文章只是想让去重方式更加严谨(ps&#xff1a;我才不会说是因为技术成长了&#xff0c;看不上之前写的…...

AI相机“妙鸭相机”原理分析和手动实现方案

妙鸭相机 一个通过上传大约20张照片&#xff0c;生成专属自拍。在2023年7月末爆火&#xff0c;根据36Kr报道&#xff0c;妙鸭相机系阿里系产品&#xff0c;挂靠在阿里大文娱体系下&#xff0c;并非独立公司。 使用方法是上传20张自拍照片&#xff0c;之后可以选择模板生成自己…...

关于计算机大学生秋招面试的那点事?(Golang篇)

前言&#xff1b; Go语言&#xff08;简称Golang&#xff09;越来越受到开发者的关注和欢迎。它由Google公司于2009年推出&#xff0c;旨在提供更好的性能和并发性能。眼下&#xff0c;越来越多的公司在使用它&#xff0c;比如著名的云计算服务商AWS&#xff0c;以及知名电商京…...

Windows网络自学的第一天:创建线程

CreateThread函数&#xff1a; 该函数用于创建一个新的线程并在其上运行指定的函数&#xff0c;原型如下&#xff1a; HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes,SIZE_T dwStackSize,LPTHREAD_START_ROUTINE lpStartAddress,LPVOID …...

正确的 Java 异常处理

我们来谈谈痛点吧。由于我的职责&#xff0c;我必须使用许多不同的服务&#xff08;进行编辑、进行代码审查......&#xff09;&#xff1b;不同的团队通常会编写所有这些服务&#xff0c;每当涉及到处理错误并从服务转发错误时&#xff0c;有时我的眼睛就会开始流泪。让我尝试…...

RTT(RT-Thread)时钟管理

目录 时钟管理 时钟节拍 RTT工程目录结构介绍 配置文件&#xff1a;rtconfig.h 获取系统节拍 获取系统节拍数函数 实例 定时器 RT_Thread定时器介绍 定时器源码分析&#xff08;了解即可&#xff09; rt_system_timer_init (硬件定时器初始化) rt_system_timer_thr…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

稳定币的深度剖析与展望

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

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...