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

2025/9/4 3:02:55 来源：https://blog.csdn.net/2303_80170533/article/details/147044605 浏览: 次关键词：数据结构 | 证明链表环结构是否存在

在这里插入图片描述
❤个人主页：

链表环结构

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;
}