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],代码的执行流程如下:

  1. front 初始化为 1

  2. 递归调用 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

  3. 最终返回 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)只会修改原本链表节点的指向

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/15744.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

INFINI Labs 产品更新 - Easysearch 增强 Rollup 能力,Console 完善 TopN 指标等

INFINI Labs 产品更新发布!此次更新,Easysearch 增强 Rollup 能力,支持更多的聚合方式;Console 完善了 TopN 的指标,支持自定义视图,并内嵌视图模板;Gateway 进行了多处优化以及修复相关 Bug 等…

仿 RabbitMQ 实现的简易消息队列

文章目录 项目介绍开放环境第三⽅库介绍ProtobufMuduo库 需求分析核⼼概念实现内容 消息队列系统整体框架服务端模块数据管理模块虚拟机数据管理模块交换路由模块消费者管理模块信道(通信通道)管理模块连接管理模块 客户端模块 公共模块日志类其他工具类…

Node.js开发属于自己的npm包(发布到npm官网)

在 Node.js 中开发并发布自己的 npm 包是一个非常好的练习,可以帮助我们更好地理解模块化编程和包管理工具,本篇文章主要阐述如何使用nodejs开发一个属于自己的npm包,并且将其发布在npm官网。在开始之前确保已经安装了 Node.js 和 npm。可以在…

二、通义灵码插件保姆级教学-IDEA(使用篇)

一、IntelliJ IDEA 中使用指南 1.1、代码解释 选择需要解释的代码 —> 右键 —> 通义灵码 —> 解释代码 解释代码很详细,感觉很强大有木有,关键还会生成流程图,对程序员理解业务非常有帮忙,基本能做到哪里不懂点哪里。…

Python----PyQt开发(PyQt基础,环境搭建,Pycharm中PyQttools工具配置,第一个PyQt程序)

一、QT与PyQT的概念和特点 1.1、QT QT是一个1991年由The Qt Company开发的跨平台C图形用户界面应用程序开发 框架,可构建高性能的桌面、移动及Web应用程序。也可用于开发非GUI程序,比如 控制台工具和服务器。Qt是面向对象的框架,使用特殊的代…

【数据结构】双向链表(真正的零基础)

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的!在上篇我们学习了单向链表,而单向链表虽然空间利用率高,插入和删除也只需改变指针就可以达到!但是我们在每次查找、删除、访问..…

pip3命令全解析:Python3包管理工具的详细使用指南

pip3命令全解析:Python3包管理工具的详细使用指南 一、基本使用二、升级和更新三、其他常用命令四、换源操作五、注意事项六、帮助信息pip3命令使用说明 pip3 是 Python 3 的包管理工具,用于安装、升级和卸载 Python 3 的包。以下是 pip3 的常用命令及详细说明: 一、基本使…

开启对话式智能分析新纪元——Wyn商业智能 BI 携手Deepseek 驱动数据分析变革

2月18号,Wyn 商业智能 V8.0Update1 版本将重磅推出对话式智能分析,集成Deepseek R1大模型,通过AI技术的深度融合,致力于打造"会思考的BI系统",让数据价值触手可及,助力企业实现从数据洞察到决策执…

使用PyCharm创建项目以及如何注释代码

创建好项目后会出现如下图所示的画面,我们可以通过在项目文件夹上点击鼠标右键,选择“New”菜单下的“Python File”来创建一个 Python 文件,在给文件命名时建议使用英文字母和下划线的组合,创建好的 Python 文件会自动打开&#…

第三个Qt开发实例:利用之前已经开发好的LED驱动在Qt生成的界面中控制LED2的亮和灭

前言 上一篇博文 https://blog.csdn.net/wenhao_ir/article/details/145459006 中,我们是直接利用GPIO子系统控制了LED2的亮和灭,这篇博文中我们利用之前写好的LED驱动程序在Qt的生成的界面中控制LED2的亮和灭。 之前已经在下面两篇博文中实现了LED驱动…

【Unity】性能优化:UI的合批 图集和优化

目录 前言一、合批测试二、图集 前言 注意:DC指的是Draw Call。 温馨小提示:Frame Debugger 窗口(菜单:Window > Analysis > Frame Debugger)会显示绘制调用信息,并允许您控制正在构建的帧的“回放”…

【安当产品应用案例100集】037-强化OpenVPN安全防线的卓越之选——安当ASP身份认证系统

在当前数字化时代,网络安全已成为企业发展的重要组成部分。对于使用OpenVPN的企业而言,确保远程访问的安全性尤为重要。安当ASP身份认证系统凭借其强大的功能和便捷的集成方式,为OpenVPN的二次登录认证提供了理想的解决方案,特别是…

表单与交互:HTML表单标签全面解析

目录 前言 一.HTML表单的基本结构 基本结构 示例 二.常用表单控件 文本输入框 选择控件 文件上传 按钮 综合案例 三.标签的作用 四.注意事项 前言 HTML&#xff08;超文本标记语言&#xff09;是构建网页的基础&#xff0c;其中表单&#xff08;<form>&…

python卷积神经网络人脸识别示例实现详解

目录 一、准备 1&#xff09;使用pytorch 2&#xff09;安装pytorch 3&#xff09;准备训练和测试资源 二、卷积神经网络的基本结构 三、代码实现 1&#xff09;导入库 2&#xff09;数据预处理 3&#xff09;加载数据 4&#xff09;构建一个卷积神经网络 5&#xff0…

防御保护-----前言

HCIE安全防御 前言 计算机病毒 ​ 蠕虫病毒----->具备蠕虫特性的病毒&#xff1a;1&#xff0c;繁殖性特别强&#xff08;自我繁殖&#xff09;&#xff1b;2&#xff0c;具备破坏性 蠕虫病毒是一种常见的计算机病毒&#xff0c;其名称来源于它的传播方式类似于自然界中…

java和vue开发的图书馆借阅管理系统小程序

主要功能&#xff1a; 学生借书还书&#xff0c;管理员管理图书管理学生借书还书。系统显示在馆数量和图书总数量&#xff0c;借书时借书数量不可超过在馆数量&#xff0c;还书时需要输入归还数量&#xff08;可借2本书&#xff0c;归还的时候一本一本归还&#xff0c;可查看归…

【R】Dijkstra算法求最短路径

使用R语言实现Dijkstra算法求最短路径 求点2、3、4、5、6、7到点1的最短距离和路径 1.设置data&#xff0c;存放有向图信息 data中每个点所在的行序号为起始点序号&#xff0c;列为终点序号。 比如&#xff1a;值4的坐标为(1,2)即点1到点2距离为4&#xff1b;值8的坐标为(6,7)…

Oracle的学习心得和知识总结(三十三)|Oracle数据库数据库的SQL ID的底层计算原理分析

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《Oracle Database SQL Language Reference》 2、参考书籍&#xff1a;《PostgreSQL中文手册》 3、EDB Postgres Advanced Server User Gui…

将DeepSeek接入Excel实现交互式对话

引言 将DeepSeek接入Excel&#xff0c;为你带来前所未有的交互体验&#xff01;“哪里不懂&#xff0c;选中哪里”&#xff0c;然后直接在侧边栏对话框向DeepSeek发问&#xff0c;非常地方便&#xff01; 案例演示 设置接入方式 既可以通过本地部署的DeepSeek接入Excel&#…

在npm上传属于自己的包

最近在整理代码&#xff0c;上传到npm方便使用&#xff0c;所以学习了如何在npm发布一个包&#xff0c;整理写成一篇文章和大家一起交流。 1、注册npm账号 npm | Home 2、确保是登录状态 &#xff08;在包目录下&#xff0c;终端执行 npm login) 按enter键自动打开页面&…