检查链表是否回文

        根据回文对称的特点,不难想到将链表分成前后两部分,然后将其中一部分反转的方法。

        可以使用快慢指针的方式找到链表的中点,其中快指针每次移动两步,慢指针每次移动一步。当快指针到达链表末尾时,慢指针指向的位置即为链表的中点。

        然后将链表的后半部分反转,比较前半部分和反转后的后半部分,从而判断链表是否为回文链表。

    public boolean isPalindrome(ListNode head) {
        // 初始化快慢指针,均指向链表头部
        ListNode fast = head;
        ListNode slow = head;

        // 使用快慢指针找到链表中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 反转后半部分链表
        ListNode root = null;
        while (slow != null) {
            ListNode tmp = slow.next;
            slow.next = root;
            root = slow;
            slow = tmp;
        }

        // 比较前半部分和反转后的后半部分链表
        fast = head;
        while (root != null) {
            // 如果节点值不相等,说明链表不是回文链表,返回 false
            if (fast.val != root.val) {
                return false;
            }
            // 移动指针
            fast = fast.next;
            root = root.next;
        }

        // 遍历完成,说明链表是回文链表,返回 true
        return true;
    }

        这段代码中在处理奇数长度的链表时选择保留中间节点,当然你也可以选择舍弃比较中间节点。如下:

    public boolean isPalindrome(ListNode head){
        // 如果链表为空或只有一个节点,认为是回文链表
        if (head == null || head.next == null){
            return true;
        }

        // 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head.next;
        // 当链表长度是奇数时,循环结束时slow位于中间节点的前一个节点
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // 获取后半部分链表的头节点
        ListNode secondHalf = slow.next;
        if (fast.next != null){
            // 当链表长度是奇数时,就要多移动一步
            secondHalf = slow.next.next;
        }

        // 切断前半部分链表与后半部分链表的连接
        slow.next = null;

        // 比较前半部分和反转后的后半部分链表是否相等
        return equals(secondHalf, reverseList(head));
    }

    // 比较两个链表是否相等
    private boolean equals(ListNode head1, ListNode head2){
        while (head1 != null && head2 != null){
            if (head1.val != head2.val){
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        
        return head1 == null && head2 == null;
    }

    // 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[LeetCode周赛复盘] 第 384 场周赛20240211

[LeetCode周赛复盘] 第 384 场周赛20240211 一、本周周赛总结100230. 修改矩阵1. 题目描述2. 思路分析3. 代码实现 100219. 回文字符串的最大数量1. 题目描述2. 思路分析3. 代码实现 100198. 匹配模式数组的子数组数目 II1. 题目描述2. 思路分析3. 代码实现 参考链接 一、本周…

前端JavaScript篇之ajax、axios、fetch的区别

目录 ajax、axios、fetch的区别AjaxAxiosFetch总结注意 ajax、axios、fetch的区别 在Web开发中,ajax、axios和fetch都是用于与服务器进行异步通信的技术,但它们在实现方式和功能上有所不同。 Ajax 定义与特点:Ajax是一种在无需重新加载整个…

【c++基础】国王的魔镜

说明 国王有一个魔镜,可以把任何接触镜面的东西变成原来的两倍——只是,因为是镜子嘛,增加的那部分是反的。 比如一条项链,我们用AB来表示,不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话,魔镜会把…

小游戏和GUI编程(5) | SVG图像格式简介

小游戏和GUI编程(5) | SVG图像格式简介 0. 问题 Q1: SVG 是什么的缩写?Q2: SVG 是一种图像格式吗?Q3: SVG 相对于其他图像格式的优点和缺点是什么?Q4: 哪些工具可以查看 SVG 图像?Q5: SVG 图像格式的规范是怎样的?Q6…

中文GPTS详尽教程,字节扣子Coze插件使用全输出

今天,斜杠君和大家分享如何在字节扣子Coze中创建插件,并在创建后如何使用这个插件。 01 新建插件 首先,进入到插件页面,创建一个插件。 https://www.coze.cn/home 点击左侧的个人空间。 在上面选择”插件“标签,来到…

精灵图,字体图标,CSS3三角

精灵图 1.1为什么需要精灵图 一个网页中往往会应用很多小的背景图像作为修饰,当网页中的图像过多时,服务器就会频繁的接受和发送请求图片,造成服务器请求压力过大,这将大大降低页面的加载速度。 因此,为了有效地减少…

《计算思维导论》笔记:10.4 关系模型-关系运算

《大学计算机—计算思维导论》(战德臣 哈尔滨工业大学) 《10.4 关系模型-关系运算》 一、引言 本章介绍数据库的基本数据模型:关系模型-关系运算。 二、什么是关系运算 在数据库理论中,关系运算(Relational Operatio…

读书笔记之《运动改造大脑》:运动是最佳的健脑丸

《运动改造大脑》的作者是约翰•瑞迪(John Ratey) / 埃里克•哈格曼(Eric Hagerman),原著名称为:Spark:the revolutionary new science of exercise and the brain,于 2013年出版约翰…

Shell脚本编程

文章目录 一、简介二、变量变量命名使用变量只读变量删除变量变量种类 三、数组四、算数运算五、条件测试数值测试字符串测试文件测试组合测试 六、选择执行七、用户交互read命令 八、循环语句for循环while循环until循环 九、函数十、调试脚本十一、环境配置bash配置文件案例&a…

服务器解析漏洞及任意文件下载

1.服务器文件解析漏洞 文件解析漏洞,是指Web容器(Apache、nginx、iis等)在解析文件时出现了漏洞,以其他格式执行出脚本格式的效果。从而,黑客可以利用该漏洞实现非法文件的解析。 (1) Apache linux系统中的apache的php配置文件在/etc/apac…

备战蓝桥杯---动态规划(基础1)

先看几道比较简单的题&#xff1a; 直接f[i][j]f[i-1][j]f[i][j-1]即可&#xff08;注意有马的地方赋值为0&#xff09; 下面是递推循环方式实现的AC代码&#xff1a; #include<bits/stdc.h> using namespace std; #define int long long int a[30][30]; int n,m,x,y; …

Hive窗口函数详解

一、 窗口函数知识点 1.1 窗户函数的定义 窗口函数可以拆分为【窗口函数】。窗口函数官网指路&#xff1a; LanguageManual WindowingAndAnalytics - Apache Hive - Apache Software Foundationhttps://cwiki.apache.org/confluence/display/Hive/LanguageManual%20Windowing…

【Linux】make和Makefile

目录 make和Makefile make和Makefile 我们使用vim编辑器的时候&#xff0c;在一个文件里写完代码要进行编译&#xff0c;要自己输入编译的指令。有没有一种可以进行自动化编译的方法——makefile文件&#xff0c;它可以指定具体的编译操作&#xff0c;写好makefile文件&#x…

项目02《游戏-13-开发》Unity3D

基于 项目02《游戏-12-开发》Unity3D &#xff0c; 任务 &#xff1a;宠物系统 及 人物头像血条 首先在主面板MainPanel预制体中新建一个Panel&#xff0c; 命名为PlayerInfo 新建Image&#xff0c;作为头像 新建Slider&#xff0c;作为血条 对Panel组件添加一个水…

案例:CentOS8 在 MySQL8.0 实现半同步复制

异步复制 MySQL 默认的复制即是异步的&#xff0c;主库在执行完客户端提交的事务后会立即将结果返给给客户端&#xff0c;并不关心从库是否已经接收并处理&#xff0c;这样就会有一个问题&#xff0c;主节点如果 crash 掉了&#xff0c;此时主节点上已经提交的事务可能并没有传…

滑动窗口的最大值

题目 239. 滑动窗口最大值 - 力扣&#xff08;LeetCode&#xff09; 思路 使用一个队列充当不断滑动的窗口&#xff0c;每次滑动记录其中的最大值&#xff1a; 如何在 O(1) 时间计算最大值&#xff0c;只需要一个特殊的数据结构「单调队列」&#xff0c;push 方法依然在队尾添…

Swift 隐藏宝藏:“逆天改命”调整方法重载(function overloading)优先级

概览 在 Swift 语言中有很多隐藏“宝藏”悄悄深埋在不为人知的角落&#xff0c;静静等待着有缘秃头码农们的大力挖掘。 而在这里&#xff0c;我们将介绍 Swift 语言中一个非常有用的秘技&#xff1a;方法重载优先级判断以及如何改变它。 在本篇博文中&#xff0c;您将学到如下…

腾讯云4核8G服务器性能如何?支持多少用户访问?

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…

移动光猫gs3101超级密码及改桥接模式教程

文章目录 超级管理员账号改桥接模式路由器连接光猫&#xff0c;PPPOE拨号即可&#xff01;附录&#xff1a;如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …

奶茶点餐|奶茶店自助点餐系统|基于微信小程序的饮品点单系统的设计与实现(源码+数据库+文档)

奶茶店自助点餐系统目录 目录 基于微信小程序的饮品点单系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、商品信息管理 2、商品评价管理 3、商品订单管理 4、用户管理 四、数据库设计 1、实体ER图 2、具体的表设计如下所示&#xff1a; 五、核心代码 …