数据结构 | 证明链表环结构是否存在

❤个人主页：

链表环结构

• 0.前言
• 1.环形链表（基础）
• 2.环形链表Ⅱ（中等）
• 3.证明相遇条件及结论
• • 3.1 问题1特殊情况证明
  • 3.2 问题1普适性证明

0.前言

在这篇博客中，我们将深入探讨链表环结构的检测方法：
Floyd算法的原理：如何通过快慢指针检测环？
环入口的定位：如何找到环的起点？
通过这篇博客，我会对链表中的环结构进行相关证明解释，总结学习。

1.环形链表（基础）

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

题目描述：

代码实现：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode*slow,*fast; slow = fast = head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false;}

代码解释：

这个题目的实现逻辑比较简单，我们定义快慢指针来进行实现，fast指针每次走2步，slow指针每次走1步，当快指针和慢指针相遇的时候，如果链表中存在环，则返回 true 。否则，返回 false。

2.环形链表Ⅱ（中等）

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
题目描述：

代码实现1：

struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* fast; struct ListNode* slow; fast = slow = head; while (fast && fast->next) { //快慢指针依次走 slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* start = head; struct ListNode* meet = slow; while (meet != start) { meet = meet->next; start = start->next; } return meet; } } return NULL;}

代码解释1：

代码实现2：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* tailA=headA,*tailB=headB; int lenA=1,lenB=1; while(tailA) { tailA=tailA->next; ++lenA; } while(tailB) { tailB=tailB->next; ++lenB; } int gap=abs(lenA-lenB); struct ListNode* longlist=headA,*shortList=headB; if(lenA<lenB) { longlist=headB; shortList=headA; } while(gap--) { longlist=longlist->next; } while(longlist!=shortList) { longlist=longlist->next; shortList=shortList->next; } return longlist;}struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast; struct ListNode* slow; fast=slow=head; while(fast&&fast->next) { //快慢指针依次走 slow=slow->next; fast=fast->next->next; if(slow==fast) { //转换成求交点 struct ListNode* meet=slow; struct ListNode* lt1=meet->next; struct ListNode* lt2=head; meet->next=NULL; return getIntersectionNode(lt1,lt2); } } return NULL;}

代码解释2：

3.证明相遇条件及结论

3.1 问题1特殊情况证明

问题1: 为什么slow走1步，fast走2步，他们会相遇吗？会不会错过？请证明

3.2 问题1普适性证明

问题：为什么slow走1步，fast走3步（x>=3），他们会相遇吗？会不会错过？请证明

感谢您的阅读支持！！！
后续会持续更新的！！！
文末投票支持一下！！！