【数据结构和算法初阶(C语言)】带环链表问题详解(快慢指针的烧脑应用)

本文主要是介绍【数据结构和算法初阶(C语言)】带环链表问题详解(快慢指针的烧脑应用),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.铺垫-----带环链表基本了解

2. 题目:环形链表

 

3.环形链表||  

​编辑 3.1题解1

3.2  题解2

4.总结


1.铺垫-----带环链表基本了解

  环形链表题目启迪:

环形链表特点:遍历链表会出现一模一样的地址

 

2. 题目:环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle/

 启迪:

首先,如果是循环链表这种特殊的带环指针,那么当我们用一个指针来遍历这个链表,就会有遍历指针等于头节点停下来,就判断有环存在。

那么对于其他带环链表来说,无法判断在哪一个节点开始是环的开始节点,如何找得到两个相等的指针呢。

这里使用快慢指针的思想,既定义两个指针,如上图所表现,最终两个指针都会进入我们的环形链表中,不断的跑,如果两者的速度差控制合适,那么总有一瞬间两者就会相遇,当两者相遇就可以说明这个链表带环。那么关键在于快慢指针之间的速度差该设置为多少。

 首先,我们可以猜想快指针的速度是慢指针速度的两倍,就是说慢指针一次走一步,快指针一次走两步:

那么当我们的慢指针进入环时,如果两者目前没有相遇,那么是不是应该是快指针在追击慢指针,设慢指针刚入环时他们之间的距离为N

如果速度是三倍,同样的分析:
当慢指针进入环时:设两者的距离为N,

那么每走一次,快指针走三步,慢指针走一步,二者之间距离减少2;

N-2   N-4  N-6     N-8

如果N是偶数,最后就可以追上

如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1

每移动一次距离-2,

设c-1为N

N-2   N-4  N-6     N-8.............

如果N是偶数,最后就可以追上

如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1

那么如果c-1是奇数,就会追不上了。

解题代码:

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

 

 

3.环形链表||  

 

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle-ii/

 3.1题解1

 结论:从相遇点定义一个指针,在头结点出发一个指针,两个指针速率相同,最后会在环的入点相遇

 

 

 

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur  = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走while(meet != cur){cur = cur->next;meet = meet->next;}return cur;}}return NULL;}

 

3.2  题解2

 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * cura = headA,*curb = headB;int lena = 1;int lenb = 1;while(cura->next){cura = cura->next;lena++;//计算链表a的长度}while(curb->next){curb = curb->next;lenb++;//计算链表b的长度}//如果两个链表相交,那么尾结点的地址一定相等//所以这里就可以判断一下两个链表是否相交if(cura != curb){return NULL;}int gap = abs(lena-lenb);//计算两个链表之间的差值,用来绝对值struct ListNode*longst = headA,*shortlist = headB;if(lena<lenb){longst = headB;shortlist = headA;}while(gap--){longst = longst->next;//长的先走差距步}//同时找交点while(longst != shortlist){longst = longst->next;shortlist = shortlist->next;}return longst;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur  = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走struct ListNode * newnode = meet->next;meet->next = NULL;return   getIntersectionNode(head,newnode);}}return NULL;}

 

4.总结

带环链表的题目涉及到数学分析,从解题的过程中我们也能感知到,可以结合图解多看一下代码,结合理解。以上就是本期的所有内容,知识含量蛮多,大家可以配合解释和原码运行理解。创作不易,大家如果觉得还可以的话,欢迎大家三连,有问题的地方欢迎大家指正,一起交流学习,一起成长,我是Nicn,正在c++方向前行的奋斗者,数据结构内容持续更新中,感谢大家的关注与喜欢。

这篇关于【数据结构和算法初阶(C语言)】带环链表问题详解(快慢指针的烧脑应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/774331

相关文章

Linux线程同步/互斥过程详解

《Linux线程同步/互斥过程详解》文章讲解多线程并发访问导致竞态条件,需通过互斥锁、原子操作和条件变量实现线程安全与同步,分析死锁条件及避免方法,并介绍RAII封装技术提升资源管理效率... 目录01. 资源共享问题1.1 多线程并发访问1.2 临界区与临界资源1.3 锁的引入02. 多线程案例2.1 为

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中,分布

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

C语言中%zu的用法解读

《C语言中%zu的用法解读》size_t是无符号整数类型,用于表示对象大小或内存操作结果,%zu是C99标准中专为size_t设计的printf占位符,避免因类型不匹配导致错误,使用%u或%d可能引发... 目录size_t 类型与 %zu 占位符%zu 的用途替代占位符的风险兼容性说明其他相关占位符验证示

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

使用IDEA部署Docker应用指南分享

《使用IDEA部署Docker应用指南分享》本文介绍了使用IDEA部署Docker应用的四步流程:创建Dockerfile、配置IDEADocker连接、设置运行调试环境、构建运行镜像,并强调需准备本... 目录一、创建 dockerfile 配置文件二、配置 IDEA 的 Docker 连接三、配置 Do

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

深入浅出SpringBoot WebSocket构建实时应用全面指南

《深入浅出SpringBootWebSocket构建实时应用全面指南》WebSocket是一种在单个TCP连接上进行全双工通信的协议,这篇文章主要为大家详细介绍了SpringBoot如何集成WebS... 目录前言为什么需要 WebSocketWebSocket 是什么Spring Boot 如何简化 We

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时