python-leetcode 23.回文链表
题目:
给定单链表的头节点head,判断该链表是否为回文链表,如果是,返回True,否则,返回False
输入:head=[1,2,2,1]
输出:true
方法一:将值复制到数组中后用双指针法
有两种常用的列表实现,分别为数组列表和链表。
(1)数组列表底层是使用数组存储值,可以通过索引在O(1)的时间访问列表任何位置的值,这是基于内存寻址的方式。
(2)链表存储的是称为节点的对象,每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要O(n)的时间,因为要通过指针获取到下一个位置的节点。
确定数组列表是否回文很简单,可以使用双指针法来比较两端的元素,并向中间移动。一个指针从起点向中间移动,另一个指针从终点向中间移动。这需要O(n)的时间,因为访问每个元素的时间是O(1),而有n个元素要访问
同样的方法在链表操作上并不简单,因为不论是正向访问还是反向访问都不是O(1).而将链表的值复制到数组列表中是O(n),因此简单的方法是将链表的值复制到数组列表中,再使用双指针法判断
算法:1.将链表复制到数组列表中 2.使用双指针法判断是否为回文
第一步:遍历链表将值复制到数组列表中。,使用currentNode
指向当前节点。每次迭代向数组添加currentNode.val,并更新currentNode = currentNode.next,当currentNode = null
时停止循环
第二步:使用双指针法来检查是否为回文。在起点放置一个指针,在结尾放置一个指针,每一次迭代判断两个指针指向的元素是否相同,若不同,返回 false;相同则将两个指针向内移动,并继续判断,直到两个指针相遇。但在 Python 中,很容易构造一个列表的反向副本进行比较。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""vals=[] #初始化一个空列表来存储链表中的节点值current_node=head #创建一个指向链表头节点的引用while current_node is not None:vals.append(current_node.val) #将当前节点的值添加到列表中current_node=current_node.next #移动链表return vals==vals[::-1] #比较源列表和它的反转列表
时间复杂度:O(N)
空间复杂度:O(N)使用了一个数组列表存放链表的元素值
方法二:递归
如果使用递归反向迭代节点,同时使用递归函数外的变量向前迭代,就可以判断链表是否为回文
算法:currentNode指针先指到尾节点,由于递归的特性再从后往前进行比较。frontPointer是递归函数外的指针。若currentNode.val != frontPointer.val,则返回False,反之frontPointer向前移动并返回True。
对于输入 head = [1, 2, 2, 1]
,代码的执行流程如下:
-
front
初始化为1
。 -
递归调用
recursively_check(1)
:-
递归调用
recursively_check(2)
:-
递归调用
recursively_check(2)
:-
递归调用
recursively_check(1)
:-
递归调用
recursively_check(None)
,返回True
。
-
-
比较
1
和1
,匹配,移动front
到2
,返回True
。
-
-
比较
2
和2
,匹配,移动front
到2
,返回True
。
-
-
比较
2
和2
,匹配,移动front
到1
,返回True
。
-
-
最终返回
True
,说明链表是回文
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""self.front_pointer=head #记录链表的头节点def recursively_check(current_node=head): #定义一个递归函数,用递归遍历链表if current_node is not None: if not recursively_check(current_node.next): #递归来检查链表的下一个节点return False #任何一次递归返回False,则链表不是回文,函数返回 Falseif self.front_pointer.val !=current_node.val:#当前节点和链表前端节点的值是否相等。如果不相等,说明链表不是回文return Falseself.front_pointer=self.front_pointer.next #即指向链表的下一个节点。return True #当链表的所有节点都成功比较并且都匹配时,说明链表是回文return recursively_check()
时间复杂度:O(N)
空间复杂度:O(N)
这种方法比第一中效果还差,因为对栈帧的开销大,并且有限。
方法三:快慢指针
将链表的后半部分反转,然后将前半部分和后半部分进行比较。
算法:1找到前半部分链表的尾节点。2反转后半部分链表。3判断是否回文。4恢复链表。5返回结果
执行步骤一:计算链表节点的数量,遍历链表找到前半部分的尾节点
使用快慢指针在一次遍历中找到:慢指针一次走一步,快指针一次走两步,快慢指针同时出发。当快指针移动到链表的末尾时,慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
若链表个数为奇数,则中间的点应该属于前半部分
步骤二可以使用上一题反转链表的方式来反转链表的后半部分。
步骤三比较两个部分的值
步骤四使用步骤二的方式,反转恢复链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""if head is None: #检查链表是否为空。如果为空return True #链表显然是回文first_half_end=self.end_of_first_half(head) #调用函数,找到链表前半部分的尾节点second_half_start=self.reverse_list(first_half_end.next) #开始反转链表的后半部分result=True #用于存储链表是否为回文的结果first_position=head #从链表头开始second_position=second_half_start #从反转后的链表的头开始while result and second_position is not None: #遍历链表的前部分和反转后的后半分,直到后部分遍历完if first_position.val != second_position.val:#比较当前两个节点的值,如果不相等result=Falsefirst_position=first_position.next #分别指向前半部分和后半部分的下一个节点second_position=second_position.nextfirst_half_end.next = self.reverse_list(second_half_start)#反转后半部分链表,恢复链表的原始顺序return result #返回最终的回文判断结果def end_of_first_half(self,head): #这个方法用于找到链表的前半部分的尾节点fast=headslow=headwhile fast.next is not None and fast.next.next is not None:fast=fast.next.nextslow=slow.nextreturn slowdef reverse_list(self,head):pre=Nonecurr=headwhile curr is not None:next_node=curr.nextcurr.next=prepre=currcurr=next_nodereturn pre
时间复杂度:O(n)
空间复杂度:O(1)只会修改原本链表节点的指向
相关文章:

python-leetcode 23.回文链表
题目: 给定单链表的头节点head,判断该链表是否为回文链表,如果是,返回True,否则,返回False 输入:head[1,2,2,1] 输出:true 方法一:将值复制到数组中后用双指针法 有两种常用的列表实现&#…...

食品饮料生产瓶颈?富唯智能协作机器人来 “破壁”
在食品和饮料行业的发展进程中,诸多生产瓶颈如重复性劳动负担、复杂环境作业难题、季节性产能波动等,长期制约着企业的高效运营与进一步发展。如今,富唯智能协作机器人的出现,为这些难题提供了完美的解决方案,正逐步改…...

Golang GORM系列:GORM CRUM操作实战
在数据库管理中,CRUD操作是应用程序的主干,支持数据的创建、检索、更新和删除。强大的Go对象关系映射库GORM通过抽象SQL语句的复杂性,使这些操作变得轻而易举。本文是掌握使用GORM进行CRUD操作的全面指南,提供了在Go应用程序中有效…...
C++ labmbd表达式
文章目录 C++ Lambda 表达式详解1. Lambda 表达式的组成部分:2. Lambda 语法示例(1) 最简单的 Lambda(2) 带参数的 Lambda(3) 指定返回类型的 Lambda3. 捕获外部变量(1) 值捕获(复制)(2) 引用捕获(3) 捕获所有变量4. Lambda 在 STL 中的应用5. Lambda 作为 `std::function`6…...
《大规模动画优化(一):GPU 顶点动画的生成》
GPU 顶点动画(Vertex Animation Texture, VAT) GPU 顶点动画(Vertex Animation Texture, VAT)烘焙的核心思想是: 在 CPU 端预先计算动画顶点数据,并存储到纹理(Texture2D)中…...

【前端】几种常见的跨域解决方案
在前端开发中,跨域问题是常见的挑战。以下是几种常见的跨域解决方案: 1. Nginx反向代理 使用 Nginx 进行反向代理是解决跨域问题的一种常见方式。Nginx 会充当一个中间代理服务器,接收来自前端的请求并将其转发到实际的后端 API 服务&#…...
如何在WinForms应用程序中读取和写入App.config文件
如何在WinForms应用程序中读取和写入App.config文件 1. 添加App.config文件2. 配置App.config3. 读取App.config4. 写入App.config 在WinForms应用程序中, App.config文件是用于存储配置数据的标准方式。通过使用.NET框架提供的类库,我们可以方便地对 …...

【分布式理论7】分布式调用之:服务间的(RPC)远程调用
文章目录 一、RPC 调用过程二、RPC 动态代理:屏蔽远程通讯细节1. 动态代理示例2. 如何将动态代理应用于 RPC 三、RPC序列化与协议编码1. RPC 序列化2. RPC 协议编码2.1. 协议编码的作用2.2. RPC 协议消息组成 四、RPC 网络传输1. 网络传输流程2. 关键优化点 一、RPC…...
人工智能应用-智能驾驶精确的目标检测和更高级的路径规划
实现更精确的目标检测和更高级的路径规划策略是自动驾驶领域的核心任务。以下是一个简化的示例,展示如何使用Python和常见的AI库(如TensorFlow、OpenCV和A*算法)来实现这些功能。 1. 环境准备 首先,确保安装了以下库:…...
dynamic_cast和static_cast和const_cast
dynamic_cast 在 C 中的作用 dynamic_cast 是 C 运行时类型转换(RTTI, Run-Time Type Identification)的一部分,主要用于: 安全的多态类型转换检查类型的有效性向下转换(Downcasting)跨类层次的指针或引用…...

DEEPSEEK与GPT等AI技术在机床数据采集与数字化转型中的应用与影响
随着人工智能(AI)技术的迅猛发展,深度学习、自然语言处理等先进技术开始广泛应用于各行各业。在制造业尤其是机床行业,AI技术的融合带来了巨大的变革,尤其在机床数据采集与机床数字化方面的应用。本文将探讨DEEPSEEK、…...
高速存储文章目录
《zynq tcp万兆网和ftp协议分析-CSDN博客》 《国产fpga nvme ip高速存储方案设计_fpga 高速存储-CSDN博客》 《国微pcie switch 8748高速存储方案设计_国产pcie switch-CSDN博客》 《FPGA SATA高速存储设计-CSDN博客》 《FPGA NVME高速存储设计_690t fpga-CSDN博客》 《zy…...

车载测试工具 --- CANoe VH6501 进行Not Acknowledge (NAck) 测试
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活,除了生存温饱问题之外,没有什么过多的欲望,表面看起来很高冷,内心热情,如果你身…...

【清晰教程】通过Docker为本地DeepSeek-r1部署WebUI界面
【清晰教程】本地部署DeepSeek-r1模型-CSDN博客 目录 安装Docker 配置&检查 Open WebUI 部署Open WebUI 安装Docker 完成本地DeepSeek-r1的部署后【清晰教程】本地部署DeepSeek-r1模型-CSDN博客,通过Docker为本地DeepSeek-r1部署WebUI界面。 访问Docker官…...
Linux运维——用户管理
Linux用户管理 一、Linux用户管理要点二、常用命令2.1、groupadd2.2、groupdel2.3、groupmod2.4、groups2.5、useradd2.6、userdel2.7、passwd2.9、su2.10、sudo2.10.1、给普通用户授权 sudo2.10.2、 免密码授权 sudo 一、Linux用户管理要点 创建用户组 - 使用 groupadd删除用…...

mac下dify+deepseek部署,实现私人知识库
目前deepseek 十分火爆,本地部署实现私有知识库,帮助自己日常工作,上一篇使用工具cherry studio可以做到私人知识库。今天学习了一下,使用Dify链接deepseek,实现私人知识库,也非常不错,这里分享…...
Linux中设置开机运行指令
系统:Debian 12 使用systemd来设置开机自启动脚本或命令是一个更加现代且推荐的方法。下面是具体的步骤: 创建守护脚本 首先,你需要创建一个Shell脚本文件,比如mydaemon.sh,并在其中编写你的守护脚本逻辑。确保这个脚…...
IDEA中列举的是否是SpringBoot的依赖项的全部?在哪里能查到所有依赖项,如何开发自己的依赖项让别人使用
在 IntelliJ IDEA 中列举的依赖项并不一定是 Spring Boot 项目的全部依赖项。IDEA 通常只显示你在 pom.xml(Maven)或 build.gradle(Gradle)中显式声明的依赖项,而这些依赖项本身可能还会引入其他传递性依赖。 1. 如何…...
Ollama命令使用指南
Ollama 命令使用指南 Ollama 命令使用指南1. Ollama 命令概览2. Ollama 命令详解2.1 启动 Ollama2.2 创建模型2.3 查看模型信息2.4 运行模型2.5 停止运行的模型2.6 从注册表拉取模型2.7 推送模型到注册表2.8 列出本地模型2.9 查看正在运行的模型2.10 复制模型2.11 删除模型 3. …...

LIMO:上海交大的工作 “少即是多” LLM 推理
25年2月来自上海交大、SII 和 GAIR 的论文“LIMO: Less is More for Reasoning”。 一个挑战是在大语言模型(LLM)中的复杂推理。虽然传统观点认为复杂的推理任务需要大量的训练数据(通常超过 100,000 个示例),但本文展…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...