【数据结构与算法】环与相遇：链表带环问题的底层逻辑与工程实现

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人等方向学习者
❄️个人专栏：《C语言》《【初阶】数据结构与算法》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、带环链表
  • 1.1题目
  • 1.2 算法原理
  • 1.3 代码
  • 1.4 数学证明
    • 1.4.1 为什么带环slow与fast必定能相遇？
    • 1.4.2 fast一定只能走2步吗？可以是2步甚至更多吗？
      • 1.4.2.1 以3步为例
  • 1.4.3结论
• 二、环形链表（寻找相遇点）
  • 2.1 题目
  • 2.2 算法原理
  • 2.3 代码
  • 2.4 数学证明
    • 2.4.1 结论
• 总结与每日励志

前言

链表带环问题是数据结构中的经典考点，核心在于通过快慢指针法判断环的存在并定位入口点。本文从 LeetCode 两道真题出发，拆解快慢指针的相遇逻辑与数学推导，结合代码实现与严谨证明，清晰呈现带环链表的解题思路，帮助读者深入理解指针策略在链表问题中的灵活运用。

一、带环链表

1.1题目

链接：带环链表

注：这道题我们依旧使用高阶要求来做题

1.2 算法原理

核心思想:快慢指针 --- 相遇即为链表带环

创建两个指针 — slow和fast初始指向head,遍历链表slow每次走一步，fast每次走两步，那么就会分成两种情况：
• 链表不带环：那么fast一定可以遍历到NULL，
•链表带环：fast一定比slow先走进循环，在环内不断循环，当slow也进入循环时，如果链表带坏则与fast必定能相。

1.3 代码

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;*};*/ typedef struct ListNode* ListNode; bool hasCycle(struct ListNode *head){ ListNode slow = head; ListNode fast = head;//如果不相遇分为奇数个和偶数个 while(fast && fast->next){ slow = slow->next; fast = fast->next->next;//链表相遇 if(fast == slow)returntrue;}//能跳出循环 --- 不带环 returnfalse;}

1.4 数学证明

1.4.1 为什么带环slow与fast必定能相遇？

假设slow进环时与fast的差距为N，那么接下来就是追击问题，slow每次走一步，fast每次走两步。那么每走完一次slow的距离就会变成：N - 1，N - 2，N -3…2,1,0，故必定会相遇

1.4.2 fast一定只能走2步吗？可以是2步甚至更多吗？

1.4.2.1 以3步为例

假设slow进环时与fast的差距为N，那么接下来就是追击问题，slow每次走一步，fast每次走三步。会分成两种情况:
•当N是偶数时：N - 2，N - 4，N - 6…4，2，0
•当N是奇数时：N - 2，N - 4，N - 6…3，1，-1

也就是当N是偶数时，必定会相遇，当N是奇数时最后距离为-1，也就是会错过，如果假设圆环周长为C，那么当 N 是奇数时且fast与slow错过后进入新一轮追击，距离变为C-1，那么又会变成两个的情况：
•当N = C -1是偶数时(C为奇数)：N - 2，N - 4…4，2，0
•当N = C - 1是奇数时(C为偶数）：N - 2，N - 4…3，1，-1
综上我们可以分析出要让slow和fast不相遇只有一种可能：C为偶数且第一轮追击中N为奇数同时成立。
C为偶数且第一轮追击中N为奇数能同时满足吗？
那我们还是假设当slow进环时,slow与fast相距N:
slow走过的距离：L。
fast走过的距离为：L + C * x(x:为绕环圈数) + C - N。
slow与fast始终满足：slow = 2 * fast。
联立上面三个式子可得：2L = (x+ 1) * C - N ,我们分析可得该等式为：偶数 = （x + 1） 偶数 - 奇数不成立，故两个条件无法同时成立 ，故不会永远追不上，slow和fast必定相遇，

1.4.3结论

• 链表带环，使用快慢指针，无论fast走几步，都必定在环内与slow相遇。

二、环形链表（寻找相遇点）

2.1 题目

链接：环形链表（寻找相遇点）

2.2 算法原理

2.3 代码

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;*};*/ typedef struct ListNode* ListNode; struct ListNode *detectCycle(struct ListNode *head){ ListNode slow = head; ListNode fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;if(slow == fast){ ListNode meet = slow;while(meet != head){ meet = meet->next; head = head->next;}return meet;}}returnNULL;}

2.4 数学证明

H 为链表的起始点，E 为环入口点，M 与判环时候相遇点
设:环的长度为 R，H 到 E 的距离为 L， E 到 M 的距离为 X则: M 到 E 的距离为 R - X。在判环时，快慢指针相遇时所走的路径长度:
fast: L + X + nR
slow: L + X

注意：
当慢指针进入环时，快指针可能已经在环中绕了 n 圈了，n 至少为 1因为：快指针先进环走到 M 的位置，最后又在 M 的位置与慢指针相遇
慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针。
因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。

极端情况下，假设 n = 1，此时：L=R−X即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇

2.4.1 结论

• 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

总结与每日励志

✨本文系统梳理了带环链表的判环与入口定位方法，核心在于利用快慢指针的速度差实现相遇，再通过双指针同步遍历定位入口。每一次逻辑推导都是思维的锤炼，每一行代码都是能力的沉淀。愿你在技术之路上保持热爱与专注，以严谨态度攻克难题，永远相信美好的事情即将发生，用坚持书写属于自己的精彩。