数据结构刷题训练——链表篇(二)

目录

前言

1.题目一:链表分割

1.1 思路

1.2 分析

 1.3 题解

2. 题目二:相交链表

2.1 思路

2.2 分析

2.3 题解

3. 题目三:环形链表

3.1 思路

3.2 分析

3.3 题解

总结


前言

        本期继续分享链表相关的OJ题目,在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步提高解题能力。同时,我们也将分享一些刷题技巧和经验,帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践,相信读者可以在数据结构领域取得长足的进步。


1.题目一:链表分割

题目描述:

 题目链接:

链表分割icon-default.png?t=N6B9https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

1.1 思路

        这道题目没有示例,这也是这道题的难点之一,我们只根据题意自己寻找示例,进行分析。题目的意思是说,给一个链表,给一个x值,把小于x的插入到x前边,大于x的插入到x的后边,且不可以打乱原链表中的次序(链表中的数据大小为乱序)。理解了题意,大家可以先自己思考一下解题思路。

        对于这道题的要求我们可以这样做:遍历原链表,将大于等于x的尾插到一个新链表,小于x的尾插到一个新链表,最后将两个链表合并。

1.2 分析

        这道题思路虽然非常简单,但是在实际编写代码时会有很多的坑。例如要考虑链表为NULL的情况,如果原链表中的所有值都大于x或小于x那就会造成两个链表中,其中一个链表为NULL。

 假设原链表为:

 x值为3,那我们就可以把原链表分割成以下两个链表:

         这道题目有两种方法,一种是使用带头节点的链表,一种是使用不带头节点的链表。对于链表掌握不熟悉的,本人推荐使用带头节点的链表,当然带头节点的链表对于这道题也可以简化代码。如果没有带头节点,那我们在初始化后尾插时就需要进行特殊处理。相对比较麻烦,所有我们这里推荐使用带头链表。

        如果带头结点两链表就是这样的:

 将两个链表合并时也不需要特殊处理可以直接连接,如下图:

 不用担心头节点怎么办,两个头节点最后会被销毁,销毁之后就是我们所需要的链表了。

         就算是第一个链表为空,也可以搞定:

         连接的时候也不需要特殊处理,最后销毁两个头节点即可。

 1.3 题解

根据分析的思路,我们对代码进行编写:

ListNode* partition(ListNode* pHead, int x) {struct ListNode* head1,*head2,*tail1,*tail2;head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));//创建两个头节点head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=pHead;    while(cur)                    //遍历原链表{if(cur->val < x)          //小于x就尾插到链表1{tail1->next=cur;tail1=tail1->next;}else                      //大于等于x就尾插到链表2{tail2->next=cur;tail2=tail2->next;}cur=cur->next;            }tail1->next=head2->next;      //将两个链表合并tail2->next=NULL;struct ListNode* head=head1->next;free(head1);free(head2);return head;                  //最后返回链表1的第一个节点}

2. 题目二:相交链表

题目描述:

 示例:

 题目链接:

相交链表icon-default.png?t=N6B9https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

2.1 思路

        这道题目的解题思路就简单了,但要注意链表长度不同的情况。当两个节点的节点个数不相同时,指向长链表的指针要先走它们节点个数的差值步。然后开始一一对比,直到遇到相交节点为止。

2.2 分析

        链表相交并不是像直线那样交叉相交,单链表中,一个节点只能指向一个节点,所有这里的链表相交是如下图的情况:

 总体分 3 步:

  • 先遍历两个链表得到两个链表的长度。
  • 长的链表先走差距步(len1-len2)。
  • 开始遍历两个数组,直到相交点,返回相交的节点

2.3 题解

整理完思路后,根据分析的思路进行编写代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB)        //如果遍历到最后两个链表的尾节点不是同一个节点就说明不相交。{return NULL;}int t= abs(lenA-lenB);//求出差距步  abs是求绝对值的函数struct ListNode* longlist=headA, *shortlist=headB;if(lenB>lenA)           //这里先假设链表A长,如果不是链表A长就交换一下,简化代码{longlist=headB;shortlist=headA;}while(t--)              //长的链表走差距步{longlist=longlist->next;}while(longlist!=shortlist)//两链表同时遍历{longlist=longlist->next;shortlist=shortlist->next;}return longlist;          //循环停止时指向的节点就是第一个相交节点,返回它们两个任意一个
}

3. 题目三:环形链表

题目描述:

 示例:

 题目链接:

环形链表icon-default.png?t=N6B9https://leetcode.cn/problems/linked-list-cycle/description/

3.1 思路

         我们知道循环链表,循环链表的尾指向链表的头,遍历一遍之后会回到链表的头,但这道题属于带环链表,带环链表的尾不一定连接着头,它可能连接着任意节点。带环链表的题目属于链表中较为复杂的题目,那要如何判断一个链表是否带环呢?

        首先我们知道,带环链表在向后遍历的时候,一定会回到入环点,比较链表中的节点是否为入环时的节点就可以了,但是问题来了,我们怎么知道哪个是开始入环的节点?不知道入环的节点又怎么比较是否是同一个节点。显然传统的思路行不通,那我们就来换一种方法。

        这里我们就可以使用快慢指针的方法,一个指针走的快一个指针走的慢,当快的指针再次与慢指针相遇,那就说明这个链表一定是带环链表。

3.2 分析

        带环链表的入环节点可能是任意节点:

         它也可以指向它自己。

        这里我们可以使用快慢指针的方法,使用快指针来追击慢指针,当快指针与慢指针再次相遇,这就说明这个链表一定为带环链表,但是如果快指针走到了NULL,这就说明这个链表不是带环链表。

3.3 题解

 根据分析的思路,我们整理一下,形成代码:

bool hasCycle(struct ListNode *head) {struct ListNode* fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;
}

         题解也是非常简单。对于带环链表,今天这道题目属于热身,下期我会专门出一期带环链表的题目。


 

总结

        最后,感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力,不断探索和挑战,成为数据结构领域的行家里手!

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

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

相关文章

elasticsearch简单入门语法

基本操作 创建不同的分词器 ik_smart&#xff1a; 极简分词 &#xff1b; ik_max_word: 最细力再度分词 基本的rest命令 methodurl地址描述PUTlocalhost:9200/索引名称/类型名称/文档id创建文档&#xff08;指定文档id&#xff09;POSTlocalhost:9200/索引名称/类型名称创建文…

蝉妈妈:2023年抖音电商半年报(附下载)

关于报告的所有内容&#xff0c;公众【营销人星球】获取下载查看 核心观点 平台流量竞争从愈发激烈变为趋于愈加缓和商家直攝总时长与观众君播总时长的总体趋势并没有愈加激烈&#xff0c;从23年上半年各自流量的同比增速来看&#xff0c;观众看摄总时长增速高于商家直攝总时…

电脑合上盖子无线网络不会断开

控制面板\硬件和声音\电源选项\系统设置 最终选择不会采取任何操作 选择不会采取任何操作

Cocos Creator的 Cannot read property ‘applyForce‘ of undefined报错

序&#xff1a; 1、博主是看了这个教程操作的时候出的bug>游戏开发 | 17节课学会如何用Cocos Creator制作3D跑酷游戏 | P9 代码控制对象移动_哔哩哔哩_bilibili 2、其实问题不是出在代码上&#xff0c;但是发现物体就是不平移 3、node全栈的资料》node全栈框架 正文…

逆向破解学习-雷电星海战歌

apk 雷电星海战歌 https://download.csdn.net/download/AdrianAndroid/88200826 安装apk&#xff0c;并试玩 # 通过关键字搜索jad 找到统一支付接口 找到匿名内部类的名称 Hook代码 public class HookComAstPlane extends HookImpl {Overridepublic String packageNam…

竞赛项目 深度学习手势识别算法实现 - opencv python

文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习手势识别算法实现 - opencv python 该项目较为新颖…

LeetCode 31题:下一个排列

目录 题目 思路 代码 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序…

Jenkins 中 shell 脚本执行失败却不自行退出

Jenkins 中 执行 shell 脚本时&#xff0c;有时候 shell 执行失败了&#xff0c;或者判断结果是错误的&#xff0c;但是 Jenkins 执行完成后确提示成功 success 。 此时&#xff0c;可以通过条件判断来解决这个问题&#xff0c;让 Jenkins 强制退出并提示执行失败 failed 。 …

Nginx使用proxy_cache指令设置反向代理缓存静态资源

场景 CentOS7中解压tar包的方式安装Nginx&#xff1a; CentOS7中解压tar包的方式安装Nginx_centos7 tar文件 怎么load_霸道流氓气质的博客-CSDN博客 参考上面流程实现搭建Nginx的基础上&#xff0c;实现静态资源的缓存设置。 注意上面安装时的目录是在/opt/nginx目录下&…

win10 + VS2022 安装opencv C++

最近需要用到C opencv&#xff0c;看了很多帖子都需要自己编译opencv源码。为避免源码编译&#xff0c;可以使用VS来配置opencv C。下面是主要过程&#xff1a; 目录 1. 从官网下载 opencv - Get Started - OpenCV 2. 点击这个exe文件进行安装 3. 配置环境变量 4. VS中的项…

java spring cloud 企业电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展 tbms

​ 项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以…

Word转PDF工具哪家安全?推荐好用的文件格式转换工具

Word文档是我们最常见也是最常用的办公软件&#xff0c;想必大家都知道了Word操作起来十分的简单&#xff0c;而且功能也是比较齐全的。随着科技的不断进步&#xff0c;如今也是有越来越多类型的办公文档&#xff0c;PDF就是其中之一&#xff0c;那么word转pdf怎么转?Word转PD…

DSP学习笔记

TI公司提供的c/c编译器&#xff0c;可以将其变成dsp语言。char类型本来是8位&#xff0c;在dsp里面是16位&#xff0c;int也是16位&#xff0c;long才是32位&#xff0c;float也是32位&#xff0c;enum是16位&#xff0c;double32位&#xff0c;long double是32位&#xff0c;p…

客户端脚本安全

客户端脚本安全 白帽子讲web安全 ———— a.了解web安全测试的基本知识 b.掌握前端的脚本安全知识&#xff0c;了解基本的前端安全测试条目&#xff0c;如同源策略、xss攻击测试、CSRF测试、点击劫持测试 c.webinsepct nessus 绿盟扫描 数据流 输入输出 浏览器安全 同源…

【HCIP】重发布实验

题目&#xff1a; 配置&#xff1a; R1 //配置ip地址 [r1]int g0/0/0 [r1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [r1-GigabitEthernet0/0/0]int g0/0/1 [r1-GigabitEthernet0/0/1]ip add 13.1.1.1 24 [r1-GigabitEthernet0/0/1]int lo0 [r1-LoopBack0]ip add 1.1.1.1 24 /…

MySQL—日志

这里写目录标题 undo logundo log的作用undo log页记录的是什么 Buffer Pool为什么需要Buffer PoolBuffer Pool缓存什么 redo log什么是redo logredo log的作用redo log什么时候刷盘undo和redo的区别 binlogbinlog 作用redo log和binlog区别如果数据数据被删了&#xff0c;能用…

【redis】redis的认识和安装

目录 1.redis是什么2.Redis的特点3.安装redis4.设置远程连接4.1 开启隧道4.2 可视化客户端连接4.3 开启防火墙 5.redis常见数据类型5.1 redis的一些全局命令5.2 数据结构 6. redis的典型应用---缓存&#xff08;cache&#xff09;6.1 使用redis做缓存6.2 缓存穿透&#xff0c;缓…

并发——Atomic 原子类总结

文章目录 1 Atomic 原子类介绍2 基本类型原子类2.1 基本类型原子类介绍2.2 AtomicInteger 常见方法使用2.3 基本数据类型原子类的优势2.4 AtomicInteger 线程安全原理简单分析 3 数组类型原子类3.1 数组类型原子类介绍3.2 AtomicIntegerArray 常见方法使用 4 引用类型原子类4.1…

wordpress数据表中标签和分类如何区分?

wordpress中标签和分类是什么关系怎么区分&#xff1f;最后有一个群的网友告诉了我文章ID和标签ID的关系是放在了wp_term_relationships表中&#xff0c;然后我百度了下这个表的结构和相关介绍&#xff0c;发现果然如此&#xff0c;先把文章保存起来&#xff1a; wp_term_rela…

EasyPoi导出 导入(带校验)简单示例 EasyExcel

官方文档 : http://doc.wupaas.com/docs/easypoi pom的引入: <!-- easyPoi--><dependency><groupId>cn.afterturn</groupId><artifactId>easypoi-spring-boot-starter</artifactId><version>4.0.0</version></dep…