OR36 链表的回文结构 题解
题目描述:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900
测试样例:
1->2->2->1 返回:true
题解思路:
- 找到中间节点;
- 在利用翻转链表的方法,将以中间节点(newList)为新的头节点来翻转链表;
- 通过遍历比较两个链表的各个值:如果对应有一个节点的数值不相等,就返回false;如果所以节点的数值都相等,就返回ture。
代码:
struct ListNode* midNode(ListNode* head)
{struct ListNode* fast = head, *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;while(n2 != NULL){n2->next = n1;n1 = n2;n2 = n3;if(n3 != NULL){n3 = n3->next;}}return n1;
}
bool chkPalindrome(ListNode* A) {// 找到中间节点struct ListNode* mid = midNode(A);// 翻转链表struct ListNode* newHead = reverseList(mid);// 比较struct ListNode* cur1 = A, *cur2 = newHead;while(cur1 && cur2){if(cur1->val != cur2->val){return false;}else {cur1 = cur1->next;cur2 = cur2->next;}}return true;}


注:
如果你还想知道回文数是如何判断的可以看一下,这一篇博客:http://t.csdn.cn/giq9u
翻转链表方法详细解释:http://t.csdn.cn/BLwnA
找链表中间节点:http://t.csdn.cn/uYTNe
本次内容到此结束了!如果你觉得这篇博客对你有帮助的话 ,希望你能够给我点个赞,鼓励一下我。感谢感谢……
相关文章:
OR36 链表的回文结构 题解
题目描述:链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结…...
“去没有天花板的地方” | 小红书用户情绪数据
最近,话题#人就要待在没有天花板的地方#社媒讨论度居高不下,小红书相关话题近90天互动量超百万。 生活的无常之外,越来越多人渴望与大自然更深层次的链接,以此寻找情绪的不同出口。或许,剖析这些情绪的生成机理&#x…...
Java文件操作(遍历目录中的文件,找到并删除有指定关键字的文件)
对于通过java对文件继续读取和写入的操作推荐看读取文件和写入文件操作 题目 扫描指定目录中的文件,并找到名称中包含指定字符的所有普通文件(不包括目录),并后续询问用户是否要删除该文件 题目分析 实际上题目就要求我们对一个…...
MySQL单表查询
单表查询 素材: 表名:worker-- 表中字段均为中文,比如 部门号 工资 职工号 参加工作 等 CREATE TABLE worker ( 部门号 int(11) NOT NULL, 职工号 int(11) NOT NULL, 工作时间 date NOT NULL, 工资 float(8,2) NOT NULL, 政治面貌 varch…...
苹果正在测试新款Mac mini:搭载M3芯片 配备24GB大内存
据悉苹果目前正在测试新的Mac机型,亮点是采用最新的M3芯片。 据报道,首款搭载M3芯片的设备应该是13英寸的MacBook Pro和重新设计的MacBook Air,Mac mini机型并不在名单上。 M3和M2同样拥有最多8个核心,分别为4个性能核和4个能效核…...
redis的缓存更新策略以及如何保证redis与数据库的数据一致性
redis的缓存更新策略有这么几种: 1、由应用直接和redis以及数据库相连接: 查询数据时,应用去redis中查询,查不到的话再由应用去数据库中查询,并将查询结果放在redis; 更新数据时ÿ…...
k8s--使用cornJob定时执行sql文件
CronJob apiVersion: batch/v1beta1 kind: CronJob metadata:name: hello spec:schedule: "0 * * * *"jobTemplate:spec:template:spec:containers:- name: postgres-alpineimage: xxxximagePullPolicy: IfNotPresentcommand:- psql- -h- 数据库服务地址- -d- 数据库…...
Qt事件过滤器
1 介绍 事件过滤器是一种机制,当某个QObject没有所需要的事件功能时,可将其委托给其它QObject,通过eventFilter成员函数来过滤实现功能。 2 主要构成 委托: ui->QObject1->installEventFilter(QObject2); eventFilter声明 …...
Java基础集合框架学习(上)
文章目录 初识基础框架为什么使用集合框架集合框架的继承关系ArrayList入门案例单元测试和增删改查单元测试的注意事项LinkedList入门案例ArrayList底层是数组LinkedList底层是链表ArrayList和LinkedList选型ArrayList存放DOG对象 初识基础框架 Java基础集合框架是Java编程语言…...
北京多铁克FPGA笔试题目
1、使用D触发器来实现二分频 2、序列检测器,检测101,输出1,其余情况输出0 module Detect_101(input clk,input rst_n,input data, //输入的序列output reg flag_101 //检测到101序列的输出标志 );parameter S0 2d0;S1 2d1;S2 2d2;S4 …...
从初学者的角度来理解指针常量和常量指针
重新理解指针常量,常量指针 应用 我先提一个问题:知道指针常量,常量指针存在的作用是什么吗? 先了解它们存在的作用再去理解它们,或许更轻松些。 比如配置文件读取:在许多工程中,配置文件用于…...
C# OpenCvSharp 去水印 图像修复
效果 项目 VS2022.net4.8OpenCvSharp4 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Security.Cryptography; using System.Text; usi…...
考研算法第40天:众数 【模拟,简单题】
题目 本题收获 又是一道比较简单的模拟题,就不说解题思路了,说一下中间遇到的问题吧,就是说cin输入它是碰到空格就停止输入的,详细的看下面这篇博客对于cin提取输入流遇到空格的问题_while(cin) 空格_就是那个党伟的博客-CSDN博…...
MySQL:内置函数、复合查询和内外连接
内置函数 select 函数; 日期函数 字符串函数 数学函数 其它函数 复合查询(多表查询) 实际开发中往往数据来自不同的表,所以需要多表查询。本节我们用一个简单的公司管理系统,有三张 表EMP,DEPT,SALGRADE来演示如何进行多表查询…...
【HTML】label 标签
在HTML中,<label> 标签用于为表单元素创建标签文本或标题。它可以与输入字段(如文本框、单选按钮、复选框等)和其他表单元素关联起来,以提高可用性和可访问性。 <label> 元素有两种常见的用法: 包裹方式…...
python视频流截图(按帧数)
一、安装opencv计算机视觉库 pip install opencv-python二、视频流截图 1、读取视频文件,获取视频帧数 import cv2 # 视频位置 video_path path_file_name # 读取视频 cap cv2.VideoCapture(video_path) # 获取视频总帧数 frame_count cap.get(cv2.CAP_PROP_F…...
MongoDB SQL
Microsoft Windows [版本 6.1.7601] 版权所有 (c) 2009 Microsoft Corporation。保留所有权利。C:\Users\Administrator>cd C:\MongoDB\Server\3.4\binC:\MongoDB\Server\3.4\bin> C:\MongoDB\Server\3.4\bin> C:\MongoDB\Server\3.4\bin>net start MongoDB 请求的…...
node js连接mysql数据库
首先,确保你已经安装了 mysql2 模块。如果没有安装,可以使用以下命令进行安装: npm install mysql2创建一个 Node.js 脚本,例如 connectToMysql.js,并使用以下代码: const mysql require(mysql2);// 创建…...
通过Python模拟计算附近WIFI密码,没有我蹭不到的网
前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 今天来分享一下如何通过 Python 脚本实现 WIFI 密码的自动猜解 无图形界面 先来看看怎么实现没有图形界面版的自动猜解。 WIFI猜解 导入模块 import pywifi from pywifi import const import time import datetime测试连…...
ubuntu20.04 远程桌面配置记录【亲测好用】
简介 ubuntu系统下有好几种不同方式的远程桌面方式,本人都使用过,以下是一些使用总结: vnc4server:其中vnc4server对gnome桌面支持不好 vino:系统自带,但需要用户登录一次后才能远程,并且需要安…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
