当前位置: 首页 > news >正文

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

 👑个人主页:啊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,简化了代码

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

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

相关文章:

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

&#x1f451;个人主页&#xff1a;啊Q闻 &#x1f387;收录专栏&#xff1a;《数据结构》 &#x1f389;前路漫漫亦灿灿 前言 今日的习题是关于链表的&#xff0c;分别是链表的回文结构和相交链表的判断。 链表的回文结构 题目为&#xff1a;链表的回文结…...

5个常见的前端手写功能:New、call apply bind、防抖和节流、instanceof、ajax

实现New 首先创建一个新的空对象设置原型&#xff0c;将对象的原型设置为函数的prototype对象让函数的this指向这个对象&#xff0c;执行构造函数的代码判断函数的返回值类型&#xff0c;如果是值类型&#xff0c;返回创建的对象。如果是引用类型&#xff0c;就返回这个引用类…...

WPF 跨线程-Dispatcher:详解与示例

在 WPF 应用程序中&#xff0c;UI 线程负责处理用户界面元素的所有操作&#xff0c;例如绘制、布局和事件处理。由于 WPF 控件是线程敏感的&#xff0c;只能在 UI 线程上访问它们。如果我们想在后台线程中执行 UI 操作&#xff0c;我们就需要使用 Dispatcher 来确保这些操作在正…...

[c++][netcdf]通过c\c++读取字段的scale_factor与add_offset

函数&#xff1a;c void readScaleAndOffset(const char* FileName,const char* VarName) {NcFile dataFile(FileName, NcFile::read);NcVar Varf dataFile.getVar(VarName);//查看维度cout << "XSizef" << Varf.getDim(0).getSize() << endl;co…...

技术速递|.NET 智能组件简介 – AI 驱动的 UI 控件

作者&#xff1a;Daniel Roth 排版&#xff1a;Alan Wang AI 的最新进展有望彻底改变我们与软件交互和使用软件的方式。然而&#xff0c;将 AI 功能集成到现有软件中可能面临一些挑战。因此&#xff0c;我们开发了新的 .NET 智能组件&#xff0c;这是一组真正有用的 AI 支持的 …...

保护C#代码的艺术:深入浅出代码混淆技术

摘要 在C#开发中&#xff0c;代码的保护是一个不可忽视的问题。本文深入探讨了几种常用的C#代码混淆工具&#xff0c;帮助开发者理解如何有效地保护代码不被反编译。同时&#xff0c;本文也对混淆技术的优缺点进行了分析&#xff0c;并提供了一些实际使用的建议。 引言 C#是…...

多线程CountDownLatch使用

1、简介 CountDownLatch是一个同步工具类&#xff0c;用来携调多个线程之间的同步&#xff0c;它是是使用一个计数器进行实现的&#xff0c;计数器初始值为线程数量。当每一个线程完成自己任务后&#xff0c;计数器的值就会减1。当计数器的值为0时&#xff0c;表示所有的线程都…...

高校心理教育辅导系统|基于Springboot的高校心理教育辅导系统设计与实现(源码+数据库+文档)

高校心理教育辅导系统目录 目录 基于Springboot的高校心理教育辅导系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、学生功能模块的实现 &#xff08;1&#xff09;学生登录界面 &#xff08;2&#xff09;留言反馈界面 &#xff08;3&#xff09;试卷列表界…...

Rockchip Android13 Vold(三):App层

目录 前言 一:处理Volumes 1、接收StorageVolume 2、创建MediaVolume 3、附加MediaVolume...

数据结构——单链表(C语言版)

文章目录 一、链表的概念及结构二、单链表的实现SList.h链表的打印申请新的结点链表的尾插链表的头插链表的尾删链表的头删链表的查找在指定位置之前插入数据在指定位置之后插入数据删除pos结点删除pos之后的结点销毁链表 三、完整源代码SList.hSList.ctest.c 一、链表的概念及…...

:app debug:armeabi-v7a failed to configure C/C++

报错信息 由于刚换电脑不久&#xff0c;新建native c工程时&#xff0c;出现报错如下&#xff1a; :app debug:armeabi-v7a failed to configure C/C null java.lang.NullPointerExceptionat com.android.build.gradle.tasks.CmakeQueryMetadataGenerator.getProcessBuilder(…...

计算机网络——应用层(4)DHCP和套接字编程

一、动态主机配置协议DHCP 1、关于协议配置&#xff1a; 在协议软件中&#xff0c;给协议参数赋值的动作就叫协议配置一个协议软件在使用前必须已被正确配置&#xff0c;具体的配置信息取决于协议栈连接到互联网的计算机的协议软件需要正确配置的参数包括①IP地址&#xff1b…...

TF-IDF演算法(Term Frequency - Inverse Document Frequency)最好懂筆記

前情提要 BoW (Bag of Words) 演算法 假设现在有M篇文章&#xff0c;一共使用了N个词汇&#xff08;term&#xff09;&#xff0c;我们就可以将文章转换成以下类型的矩阵&#xff0c;其中column1和row1的“10”表示“文章1”中出现了10次“词汇1”&#xff0c;“文章1”也可以…...

2024年4月最新版GPT

2024年4月最新版ChatGPT/GPT4, 附上最新的使用教程。 随着人工智能技术的不断发展&#xff0c;ChatGPT和GPT4已经成为了人们日常生活中不可或缺的助手。2024年4月,OpenAI公司推出了最新版本的GPT4,带来了更加强大的功能和更加友好的用户体验。本文将为大家带来最新版GPT4的实用…...

机器学习——模型评价

概述 在机器学习中&#xff0c;模型评价是评估和比较不同模型性能的关键步骤之一。它是通过对模型的预测结果与真实标签进行比较&#xff0c;从而量化模型的预测能力、泛化能力和稳定性。模型评价旨在选择最佳的模型&#xff0c;理解模型的行为&#xff0c;并为模型的改进提供…...

ARP代理

10.1.0.1/8 和10.2.0.1/8是在同一个网段 10.1.0.2/16 和10.2.0.2/16 不在同一个网段 10.1.0.1/8 和10.1.0.2/16 是可以ping通的 包发出来了&#xff0c;报文有发出来&#xff0c;目的地址是广播包 广播请求&#xff0c;发到路由器的接口G 0/0/0 target不是本接口&#xff0…...

手写前端控制并发任务

思路&#xff1a; 主要通过异步等待队列执行的原理。 当前执行的任务数达到最大值的时候&#xff0c;再继续执行的任务会放入等待队列里&#xff0c;直到当前任务执行结束后&#xff0c;减少一个当前任务数&#xff0c;并且判断队列中是否有任务&#xff0c;如果有则按顺序执…...

好用的Python开发工具合集

​ Python是一种功能强大且易于学习的编程语言&#xff0c;被广泛应用于数据科学、机器学习、Web开发等领域。随着Python在各个领域的应用越来越广泛&#xff0c;越来越多的Python开发工具也涌现出来。但是&#xff0c;对于新手来说&#xff0c;选择一款合适的Python开发工具可…...

近屿智能全新推出AI培训产品:AIGC大模型工程师与产品经理学习路径图

如今&#xff0c;人工智能和自然语言处理技术的发展&#xff0c;使得AI生成的内容&#xff08;AIGC&#xff0c;AI Generated Content&#xff09;领域开发出了巨大的潜力。就像业内巨头OpenAI公司&#xff0c;开发出了一系列自然语言处理模型ChatGPT&#xff0c;不仅带动了全世…...

Vue 3中的反向代理 和如何在服务器配置反向代理

如何在Vue 3项目中配置反向代理&#xff0c;让前端开发变得爽到爆&#xff01;还有个小插曲&#xff0c;Vite为我们提供了更简单的方式&#xff0c;就像找对象一样直接。 首先&#xff0c;我们来谈谈反向代理是什么。简单来说&#xff0c;反向代理就像是前端和后端之间的婚姻介…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...