本文主要是介绍【数据结构和算法初阶(C语言)】带环链表问题详解（快慢指针的烧脑应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1.铺垫-----带环链表基本了解
2. 题目：环形链表
3.环形链表||
编辑 3.1题解1
3.2 题解2
4.总结
1.铺垫-----带环链表基本了解
环形链表题目启迪：
环形链表特点：遍历链表会出现一模一样的地址
2. 题目：环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://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。https://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语言)】带环链表问题详解（快慢指针的烧脑应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
