【牛客网】:链表的回文结构(提升)

🎁个人主页:我们的五年

🔍系列专栏:每日一练

🌷追光的人,终会万丈光芒

 

目录

🏝问题描述:

🏝问题分析:

 步骤一:查找链表的中间节点

步骤二:对包括中间节点以后的节点进行逆置

 步骤三:两个头指针相互往后遍历

🏝节点为计数时分析:

🏝最终代码:


 前言:

这道题在链表中属于较难的题目,但是题目中我们用已经学过得基本步骤去改一下就很简单了,这道题应用的基本步骤就是:

●查找链表的中间节点

●逆置链表

这些基本步骤我都放在了这篇文章中:链表必写的四道基础题

牛客网链接:链表的回文结构_牛客题霸_牛客网

下面就让我们来看看这道题怎么解决:

🏝问题描述:

 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:

1->2->2->1
返回:true

🏝问题分析:

假如上面是一个双链表,我们只要那到链表的头节点和尾节点,然后两个头都往中间进行遍历,如果出现val不相等,我们就返回false,最后没有提前返回false,我们就返回true。

可惜上面的不是双向链表,但是我们想,单链表我们只能1>2,然后2>1,刚好和1>2和1>2相反,如果我们可以把后面的链表逆置一下,我们就可以做到前面一半也是1>2,后面一半也是1开头,然后1>2,这样就能对上了,下面我们来进行实现

先以上面的测试用例为例子:

 步骤一:查找链表的中间节点

我们先查找中间节点,如果节点个数为偶数,那么我们找到的就是中间节点的第二个节点,比如上面的例子我们找到的就是第三个节点。

查找中间节点的函数的实现:

    struct ListNode* MidNode(struct ListNode* ps)

        {

            struct ListNode* fast=ps;

            struct ListNode* slow=ps;

            if(fast&&fast->next)

            {

                fast=fast->next->next;

                slow=slow->next;

            }

            return slow;

        }

步骤二:对包括中间节点以后的节点进行逆置

实现函数:

    ListNode* reverselist(ListNode* ps)

    {

        ListNode* newhead=NULL;

        while(ps)

        {

            ListNode* pnext=ps->next;

            ps->next=newhead;

            newhead=ps;

            ps=pnext;

        }

        return newhead;

    }

对后半段的节点进行逆置以后,链表就变成这样:

 步骤三:两个头指针相互往后遍历

也就是两个1节点为头,然后每走一步,比较两个节点的val。如果不相同我们就返回false,如果相同就一直一直往后面走,走到一个为NULL为止,走到NULL还没有提前返回false,我们就返回true。

🏝节点为计数时分析:

上面我们分析的是节点为偶数个,下面我们来看看节点个数为奇数个时的情况:

 现在我们查找中间节点就是3节点,然后我们进行逆置以后,链表就变成这样了:

这种情况我们好像我们进行遍历也是没有什么问题的,所以我们只要去查找中间节点,然后进行逆置,然后遍历判断,这道题就完成了。

🏝最终代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/   
class PalindromeList {
public:
    //查找中间节点的函数
    struct ListNode* MidNode(struct ListNode* ps)
        {
            struct ListNode* fast=ps;
            struct ListNode* slow=ps;
            if(fast&&fast->next)
            {
                fast=fast->next->next;
                slow=slow->next;
            }
            return slow;
        }
    //逆置链表
    ListNode* reverselist(ListNode* ps)
    {
        ListNode* newhead=NULL;
        while(ps)
        {
            ListNode* pnext=ps->next;
            ps->next=newhead;
            newhead=ps;
            ps=pnext;
        }
        return newhead;
    }
 
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid=MidNode(A);
        struct ListNode* remid=reverselist(mid);
        //进行判断
        while(A&&remid)
        {
            if(A->val!=remid->val)
                return false;
            A=A->next;
            remid=remid->next;
        }
        return true;
    }
};

 总结:

这道题算是对链表的一个小小提升,这道题目也告诉了我,一定要学好基本的知识点,把基本的知识点用的很熟练以后,才能去解决很难得题目,后期我还会带来很多值得思考,值得我们写一写的题目。如果觉得这篇文章写的好的铁子可以点点关注,祝大家天天开心!

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

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

相关文章

C++教学——从入门到精通 11.嵌套循环及数组

上次讲到了循环,这次来讲嵌套循环 如果一个人叫你用C来画一个10*10/2cm^2三角形会么? 这就要用到嵌套循环了 来看看结构: for(变量类型1 变量;条件1;返回值1){语句1;for(变量类型 变量2;条件2;返回值2){语句2;}语句3; } 语句1,2,3是依次…

ThingsBoard远程RPC调用设备

使用 RPC 功能 客户端 RPC 从设备发送客户端 RPC 平台处理客户端RPC 服务器端 RPC 服务器端RPC结构 发送服务器端RPC 使用 RPC 功能 ThingsBoard 允许您从服务器端应用程序向设备发送远程过程调用 (RPC),反之亦然。基本上,此功能允许您向设备发送命…

关于discuz论坛网址优化的一些记录(伪静态)

最近网站刚上线,针对SEO做了些操作,为了方便网站网页被收录,特此记录下 1.开启伪静态 按照操作勾选所有项,然后点击查看伪静态规则 2.打开宝塔,找到左侧列表的网站,然后找到相应站点的设置。把discuz自动…

科普:嵌入式代码软件在环(SiL)测试的可靠性

关键词:嵌入式系统、软件在环(SiL)、测试、生命周期 01.简介 当前,嵌入式系统开发的大趋势为通过软件实现大量的硬件功能,这导致软件的复杂程度显著上升——代码开发成本和风险也成倍增加。复用已有系统中的软件组件…

【数据结构(邓俊辉)学习笔记】绪论05——动态规划

文章目录 0.前言1. Fibonacci数应用1.1 fib():递归1.1.1 问题与代码1.1.2 复杂度分析1.1.3 递归分析 1.2 fib():迭代 0.前言 make it work,make it right,make it fast. 让代码能够不仅正确而且足够高效地…

明日周刊-第7期

转眼间就又快到了五一假期,小长假有什么计划吗。封面配图是杭州高架上的月季花,非常好看。 文章目录 一周热点资源分享言论歌曲推荐 一周热点 鸿蒙系统持续扩大影响力:近期,华为官方宣布广东省已有超过600款应用加入鸿蒙系统&…

大模型的研究新方向:混合专家模型(MoE)

大模型的发展已经到了一个瓶颈期,包括被业内所诟病的罔顾事实而产生的“幻觉”问题、深层次的逻辑理解能力、数学推理能力等,想要解决这些问题就不得不继续增加模型的复杂度。随着不同应用场景的实际需求,大模型的参数会变得越来越大,复杂性和规模不断的增加,尤其是在多模…

C# 生成图形验证码

目录 应用场景 开发运行环境 设计 生成内容 生成图片 实现 核心代码 调用示例 小结 应用场景 我们当用户登录系统时经常会用到图形验证码技术,要求用户识别图片中的内容,并正确输入,方可尝试登录。类似的场景还有用户注册或者涉及…

svg图标填充渐变色及CSS鼠标悬停纯色渐变色转换

svg图标填充渐变色及CSS鼠标悬停纯色渐变色转换&#xff1a; HTML&#xff1a; <!--底部导航--> <ul class"milliaNav"> <li class"active"><a href"#"> <svg class"icon" viewBox"0 0 1024 1024&qu…

随手记:树结构翻页和定位指定数据逻辑

业务背景&#xff1a; 树形组件展示数据&#xff0c;数据包含过去数据&#xff0c;现在数据&#xff0c;未来数据&#xff0c;用户在首次进入页面时&#xff0c;展示的是当天的数据&#xff0c;如果当天没有数据&#xff0c;则显示最近一条的过去数据。数据按照时间越长数据会…

【AMBA Bus ACE 总线 5 -- Non-cached master】

文章目录 Non-cached masterNon-cached master 图 1-1 Non-cached master 意思就是,比如对于master0,它想写的时候,就直接发起transaction,它不是对自己的local cache进行操作,比如以non-shareable write 为例,master0在写的时候分别在AW,和 W channel发起命令和数据,见…

CV | 360BEV: Panoramic Semantic Mapping for Indoor Bird‘s-Eye View理解

本文主要是对于论文360BEV的解读和实现。 Paper:2023.03_360BEV: Panoramic Semantic Mapping for Indoor Birds-Eye View 360BEV&#xff1a;室内鸟瞰全景语义映射 arxiv.org/pdf/2303.11910 Code:jamycheung/360BEV: Repository of 360BEV (github.com) Demo:360BEV (jamyche…

win11 修改hosts提示无权限

win11下hosts的文件路径 C:\Windows\System32\drivers\etc>hosts修改文件后提示无权限。 我做了好几个尝试&#xff0c;都没个啥用~比如&#xff1a;右键 管理员身份运行&#xff0c;在其他版本的windows上可行&#xff0c;但是win11不行&#xff0c;我用的是微软账号登录的…

Android 组件提供的状态保存(saveInstanceState)与恢复(restoreInstanceState)

在Android的组件Activity中&#xff0c;有这样一对方法: onSaveInstanceeState 和 onRestoreInstanceState 这两对方法&#xff0c;可以让我在Activiy被异常销毁时&#xff0c;保存状态&#xff1b;以及在Activity重建时&#xff0c;恢复状态。 比如&#xff1a;当我们在输入…

就业班 第三阶段(负载均衡) 2401--4.18 day2 LVS-DR模式

3、LVS/DR 模式 实验说明&#xff1a; 1.网络使用NAT模式 2.DR模式要求Director DIP 和 所有RealServer RIP必须在同一个网段及广播域 3.所有节点网关均指定真实网关 主机名ip系统用途client172.16.147.1mac客户端lvs-server172.16.147.154centos7.5分发器real-server1172.16.…

SpringCloud简介

微服务架构理论 微服务架构概述 Spring Cloud简介Spring Cloud 技术栈SpringBoot和SpringCloud的关系SpringCloud和Dubbo区别对比相关文档 微服务架构概述 微服务是一种架构模式&#xff0c;将单一应用程序划分成一组小的服务&#xff0c;服务之间相互协调、相互配合&#xff0…

OSPF的LSA与特殊区域

Area区域概念 *一个区域维护一张LSDB&#xff0c;路由器详细的链路信息只在这个区域内传播 不是每一台路由器都需要了解所有外部目的地的详细信息 *OSPF网络的层次化设计 通过区域ID标识 骨干&#xff08; Backbone &#xff09;区域&#xff0c;必须是area 0(骨干区域…

milvus对象存储和消息中间件的工厂设计模式分析

milvus对象存储和消息中间件的工厂设计模式分析 需求 根据参数设置创建mq和storage mq有kafka,pulsar storage有local,minio,remote 配置文件 根据配置文件选择初始化mq和存储: mq:type: pulsarcommon:storageType: minio对于这种类型一个是mq&#xff0c;一个是存储&…

kubernetes部署控制器Deployment

一、概念 在学习rc和rs控制器资源时&#xff0c;这两个资源都是控制pod的副本数量的&#xff0c;但是&#xff0c;他们两个有个缺点&#xff0c;就是在部署新版本pod或者回滚代码的时候&#xff0c;需要先apply资源清单&#xff0c;然后再删除现有pod&#xff0c;通过资源控制&…

接口测试和Mock学习路线(上)

一、接口测试和Mock学习路线-第一阶段&#xff1a; 掌握接口测试的知识体系与学习路线掌握面试常见知识点之 HTTP 协议掌握常用接口测试工具 Postman掌握常用抓包工具 Charles 与 Fiddler结合知名产品实现 mock 测试与接口测试实战练习 1.接口协议&#xff1a; 需要先了解 O…