【数据结构】习题之链表的回文结构和相交链表

 👑个人主页:啊Q闻       

🎇收录专栏:《数据结构》           

 🎉前路漫漫亦灿灿

前言 

今日的习题是关于链表的,分别是链表的回文结构和相交链表的判断。

链表的回文结构 

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

这道题目没有C语言的运行环境,我们可以用C++,C++兼容C

思路为: 

 我们实现判断是否为回文结构,要先找到中间节点,然后将中间节点开始的后部分逆置,所以我们要调用前面学习过的寻找中间节点和反转链表的函数【数据结构】链表习题之链表的中间节点和合并两个有序链表-CSDN博客

【数据结构】链表习题之反转链表和删除链表中等于给定值 val 的所有节点-CSDN博客

然后比较后半部分和前半部分,判断是否相同。

代码实现:

struct ListNode*reverse(struct ListNode*head)//反转链表
{
    if(head==NULL)
    {
        return head;
    }
    struct ListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}
struct ListNode*middleNode(struct ListNode*head)//寻找中间节点
{
    struct ListNode*slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        struct ListNode*mid=middleNode(A);//将节点后部分逆置
        struct ListNode*rmid=reverse(mid);
        while(A&&rmid)//比较两部分,当有一个为空时,循环结束
        {
            if(A->val!=rmid->val)
            {
                return false;
            }
            A=A->next;
            rmid=rmid->next;
        }
        return true;
    }
};

相交链表 

题目为:. - 力扣(LeetCode)

思路为:

注意:我们比较的是节点的指针,而不是节点的值,因为节点不相交的时候,其节点的值也有可能相等。 

我们可以先找A和B链表的尾节点,如果尾节点相同,则代表这两个链表一定相交,然后我们再求长度差,让长的链表先走长度差,长的链表走完长度差后,A和B两个链表再一起走。


时间复杂度分析:我们利用这种方法,其时间的复杂度为:遍历A链表为N,遍历B链表为N,然后减去长度差后再一起遍历为N,N+N+N=3N,即O(N)。


在这个代码的实现过程中,我们会用到假设法,来简化长短链表的判断,是一个很实用的方法。

代码实现:

 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*curA=headA;
    struct ListNode*curB=headB;
    int lenA=0;
    int lenB=0;
    while(curA->next)//A和B链表遍历找尾节点
    {
        ++lenA;
        curA=curA->next;
    }
    while(curB->next)
    {
        ++lenB;
        curB=curB->next;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int gap=abs(lenA-lenB);//abs为绝对值
    //假设法:假设A为长链表,B为短链表,然后再利用一个判断,不成立就交换
    struct ListNode*longlist=headA;
    struct ListNode*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)//长链表先走
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)//A和B链表一起走
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;//该处返回长短链表均可
}

详解:

假设法:我们用假设法,就可以不用分别去讨论A>B,还是A<B,简化了代码

 

😃感谢大家阅读,希望对你有帮助😄

如果对你有帮助的话,三连支持一下吧

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

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

相关文章

校园通用型发生网络安全事件解决方案

已知校园多教学楼、多教学机房、非标网络机房缺乏防护设备、检测设备、安全保护软件(杀软) 切断所有外网&#xff0c;断网处理!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 部署路由系统可选择爱快、routeros、openwrt。等。可将日志上传到日志分析系统。《这项非必要的》 部署开源防火…

JVM—对象的创建流程与内存分配

JVM—对象的创建流程与内存分配 创建流程 对象创建的流程图如下&#xff1a; 对象的内存分配方式 内存分配的方式有两种&#xff1a; 指针碰撞&#xff08;Bump the Pointer&#xff09;空闲列表&#xff08;Free List&#xff09; 分配方式说明收集器指针碰撞&#xff08…

Aritest+python+Jenkins解放双手iOS/Android自动化

ARITest、Python 和 Jenkins 可以结合在一起创建一个自动化测试解决方案&#xff0c;实现持续集成和持续测试的目标。以下是三者如何协同工作的基本概念&#xff1a; 1. **ARITest**&#xff1a; ARITest 是一款功能全面的自动化测试工具&#xff0c;提供 UI 自动化、接口自…

加强金融行业关键信息基础设施安全保护,有效防范网络安全风险

当前&#xff0c;随着数字化发展的不断深入&#xff0c;关键信息基础设施作为国家的重要战略资源&#xff0c;面临着国内外严峻的网络安全风险。为了确保国家安全&#xff0c;在国家发展各领域和全过程中&#xff0c;需要将安全发展贯穿始终&#xff0c;筑牢国家安全屏障。金融…

C++从入门到精通——类和对象(下篇)

1. 再谈构造函数 1.1 构造函数体赋值 在创建对象时&#xff0c;编译器通过调用构造函数&#xff0c;给对象中各个成员变量一个合适的初始值。 class Date { public:Date(int year, int month, int day){_year year;_month month;_day day;} private:int _year;int _mont…

【CSS疑难点汇总】1.bor-box失效情况总结以及高宽设置为auto的情况

1. box-sizing box-sizing是改变盒子宽高的计算方式&#xff0c;一般使用bor-box&#xff0c;消除padding和border对整个盒子的影响&#xff0c;但在没有明确给出宽高的情况下&#xff0c;box-sizing是没有效果的 1.1 box-sizing不生效的情况 1.1.1块级盒子嵌套 ​ 宽度继承…

使用快捷回复软件的好处

在现代的客服工作中&#xff0c;尤其是店铺大促期间&#xff0c;咨询量的激增往往让客服人员应接不暇。即使打字速度再快&#xff0c;也难以跟上源源不断的客流。想应对这样的情况&#xff0c;快捷回复软件就非常适合客服人员了。 以我个人正在使用的客服宝为例&#xff0c;我想…

2024年阿里云优惠合集:2核2G3M云服务器61元/年起

阿里云服务器租用价格表2024年最新&#xff0c;云服务器ECS经济型e实例2核2G、3M固定带宽99元一年&#xff0c;轻量应用服务器2核2G3M带宽轻量服务器一年61元&#xff0c;ECS u1服务器2核4G5M固定带宽199元一年&#xff0c;2核4G4M带宽轻量服务器一年165元12个月&#xff0c;2核…

Unity中图片和Base64字符串之间的转换

大家好&#xff0c;我是阿赵。   这次来讲一下在unity引擎里面&#xff0c;图片和base64字符串的互相转换问题。 一、图片传输的多种方式 有时候我们需要把图片通过网络传输发送。   在Unity里面&#xff0c;有不止一种方式可以实现&#xff0c;比如说&#xff0c;把图片的…

Python+Requests模拟发送GET请求

模拟发送GET请求 前置条件&#xff1a;导入requests库 一、发送不带参数的get请求 代码如下&#xff1a; 以百度首页为例 import requests# 发送get请求 response requests.get(url"http://www.baidu.com") print(response.content.decode("utf-8"))…

数据结构之单链表的相关知识点及应用

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a;数据结构 目录 链表的概念及结构 链表与顺序表的区别与优劣势 链表的分类 单链表的实现 单链表中增加节点 单链表中尾插数据 打印单链…

研发岗-面临统信UOS系统配置总结

第一步 获取root权限 配置环境等都需要用到root权限&#xff0c;所以我们先获取到root权限&#xff0c;方便下面的操作 下载软件 在UOS应用商店下载的所需应用 版本都比较低 安装node 官网下载了【arm64】的包&#xff0c;解压到指定文件夹&#xff0c;设置链接&#xff0…

jmeter监听器大家都会用,但我这个妙招能让你提早一小时下班!

使用过 jmeter 的同学&#xff0c;应该都会使用监听器&#xff0c;在每个监听器中&#xff0c;都会有一个“所有数据写入一个文件”的功能&#xff0c;那这个功能应该怎么用呢&#xff1f;今天&#xff0c;我们就来讲讲这个功能的使用。 几乎所有的监听器都有这样一个功能。 那…

spring boot admin搭建,监控springboot程序运行状况

新建一个spring boot web项目&#xff0c;添加以下依赖 <dependency><groupId>de.codecentric</groupId><artifactId>spring-boot-admin-starter-server</artifactId><version>2.3.0</version></dependency> <dependency&…

动态内存;

目录 1.malloc; 简要介绍&#xff1a; 如何使用&#xff1a; free函数&#xff1a; 2.calloc; 简要介绍&#xff1a; 与malloc的区别&#xff1a; 3.realloc; 简要介绍&#xff1a; 如何使用&#xff1a; 4.动态内存常见错误&#xff1b; 1.malloc; 简要介绍&#x…

M12设备端面板安装连接器板后安装(前锁)L扣

M12设备端面板安装连接器板后安装(前锁)L扣 优势 -100% 电气测试及插拔测试-对于紧凑型设备&#xff1a;可在有限空间内传输很高的功率-密封圈受过度拧紧保护&#xff0c;实现长期可靠的密封 标准 IEC61076-2-111 锁紧方式 螺纹锁紧 订单料号 P/N: L-KYF12K4Z-PG9-M-L0.…

【SERVERLESS】AWS Lambda上实操

通过Serverless的发展历程及带给我们的挑战&#xff0c;引出我们改如何改变思路&#xff0c;化繁为简&#xff0c;趋利避害&#xff0c;更好的利用其优势&#xff0c;来释放企业效能&#xff0c;为创造带来无限可能。 一 Serverless概述 无服务器计算近年来与云原生计算都是在…

「2024」React 状态管理入门

概念 简单来说&#xff0c;状态指的是某一时刻应用中的数据或界面的呈现。这些数据可能包括用户填写表单的信息、应用内的用户偏好设置、应用的页面/路由状态、或者任何其他可能改变UI的信息。 状态管理是前端开发中处理用户界面(UI)状态的过程&#xff0c;在复杂应用中尤其重…

【算法分析与设计】全排列

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 给定一个不含重复数字的整数数组 nums &#xff0c;返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例 示例 1&#xff1…

(笔记)KEIL经常碰到的错误(持续整理)

KEIL常碰到的错误 一、ERROR报错1、Build时报错 Error: L6218E2、Build时报错 error 653、Default Compiler Version 54、core_cm3.h(1213): error: unknown type name inline 二、调试与仿真1、keil5软件仿真没有实时波形2、调试模式时&#xff0c;程序前没有灰块3、Periphera…