个人网页设计说明书的设计目的,seo网站优化建议,建设项目一次公示网站,海外网络服务器#x1f381;个人主页#xff1a;我们的五年
#x1f50d;系列专栏#xff1a;数据结构
#x1f337;追光的人#xff0c;终会万丈光芒 前言#xff1a; 链表的带环问题在链表中是一类比较难的问题#xff0c;它对我们的思维有一个比较高的要求#xff0c;但是这一类…个人主页我们的五年
系列专栏数据结构
追光的人终会万丈光芒 前言 链表的带环问题在链表中是一类比较难的问题它对我们的思维有一个比较高的要求但是这一类问题分析起来也是很有趣的下面我就给大家讲一下链表的带环问题并且带上几个例题进行分析。 喜欢的铁子们可以点点关注感谢大家的支持。 1.链表的分类 ●根据链表单向双向带头不带头循环不循环可以把链表分成八种。虽然说有八种链表但是常用的只有不带头单向不循环链表带头双向循环链表。 ●但是今天我们要看的是不带头单向不循环但是内部带环的问题。 2.判断链表是否带环
【LeetCode】第141题-链接https://leetcode.cn/problems/linked-list-cycle/description/ 问题描述 实现代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* fasthead; ListNode* slowhead; while(fastfast-next) { fastfast-next-next; slowslow-next; if(fastslow) return true; } return false; } 问题分析 1.快慢指针都从头开始走慢指针一次走一步快指针一次走两步。
2.当fast进环的时候slow还在环外。
3.当slow金环的时候fast在环中的某个位置。也就是说fast和slow差了N个位置当fast和slow都进环的时候就变成了追击问题。
4.slow每次走一步fast每次走两步也就是fast去追slow把slow看成静止的fast就一次往前面走一步所以fast一定可以追上slow。
3.如果fast一次走三步slow一次走一步一定可以追上吗
这里先给出答案一定可以追上 当slow刚刚进环的时候fast在环的某个位置此时fast开始追击slow还是把slow看成静止的fast每次往相对于slow追击两步。 开始时slow与fast相差N 1.当N为偶数时 因为每次fast走三步slow走一步。也就是N每次-2。因为N为偶数所以是一定可以追上的。 2.当N为奇数环的周长为C为奇数 因为N每次都是-2所以第一次追的时候fast和slow会错过fast比slow快出了一步。 此时环的周长C为奇数那么此时fast和slow相差为C-1为偶数那么就回到第一种情况。 3.N为奇数C为偶数根据情况2fast追完一圈fast和slow相差的距离为奇数所以fast和slow会一直错过但是这种情况真的存在吗 先来看看这个等式 slow刚刚进环时 slow走过的路程为L fast走过的路程为Lk*CC-N 因为fast的速度是slow的三倍所以有3*LLk*CC-N。 2*Lk*CC-N 等式左边偶数 等式右边情况3时的情况是C为偶数N为奇数k*C为偶数C-N为奇数所以等式右边为奇数 所以这种情况是不存在的 代码分析fast一次走三步slow一次走一步 typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* fasthead; ListNode* slowhead; while(fastfast-nextfast-next-next) { fastfast-next-next-next; slowslow-next; if(fastslow) return true; } return false; } typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fasthead;ListNode* slowhead;while(fastfast-nextfast-next-next){fastfast-next-next-next;slowslow-next;if(fastslow)return true;}return false;
}
