【初探数据结构】带环链表：原理、判断与数学证明

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

一、何为带环链表

1.1 带环链表的定义

由节点构成的链式结构中存在至少一个节点，其指针域指向链表中已存在的节点，形成闭合环路。特征：

• 环路结构：尾节点不指向NULL而指向历史节点
• 遍历特性：从任意环内节点出发将陷入无限循环

1.2 典型示例

二、环路检测：Floyd判圈算法

如何判断是否为带环链表？

2.1 快慢指针实现

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) return true;
    }
    return false;
}

2.2 算法特性

• 时间复杂度：O(n)，线性扫描
• 空间复杂度：O(1)，仅用两个指针

三、数学证明与深度解析

3.1 步长差为1的必然性证明（快2步/慢1步）

• 为什么slow走一步，fast走两步它们会相遇呢？会不会错过呢？请证明。

假设slow刚进环时，fast与siow之间距离为N。

slow进环后，fast开始追击slow，它们的速度差为1，也就是说，slow每走一步，它们的距离缩小1。

fast和slow的距离：
$$N->N-1->N-2->\dots \dots ->2->1->0$$
初始条件：

• 环周长：C
• 入环前路径长：L
• 相遇时快指针绕环次数：n

运动方程：
$$\{\begin{array}{l}{v}_{\text{fast}}=2v_{\text{slow}}\\ S_{\text{fast}}=L+X+nC\\ S_{\text{slow}}=L+X\end{array}$$

推导结论：
$$2(L+X)=L+X+nC\Rightarrow L=nC-X$$

3.2 广义步长分析（快n步/慢1步）

• 为什么slow走一步，fast走n（n>=3）步它们会相遇呢？会不会错过呢？请证明。

假设slow刚进环时，fast与siow之间距离为N，slow每走一步，fast走3步。

slow进环后，fast开始追击slow，它们的速度差为1，也就是说，slow每走一步，它们的距离缩小2。

分情况讨论：

1. N为偶数
   fast和slow的距离：
   $$N->N-2->N-4->\dots \dots ->2->1->0$$
   可以追上

2. N为奇数

    N -> N-2 -> N-4 ->……-> 3 -> 1 -> -1
    
    fast跳到slow前面第一个位置，此时N发生变化,进行新的一轮追击。
    
    假设环的周长为C,新的距离为N2=C-1 
    
    	再次分情况讨论：
    1. N2为偶数
    	fast和slow的距离
    	
    	N2 -> N2-2 -> N2-4 ->……-> 2 -> 1 -> 0
    	可以追上
    	
    2. N2为奇数
    
    	N2 -> N2-2 -> N2-4 ->……-> 3 -> 1 -> -1
    	
    	fast又跳到slow前面第一个位置
    	这里没必要继续进行追击了，因为C是定值，C-1的奇偶性是已经确定了的，是奇数的话永远无法追上。
   

设速度差为(n-1)，相遇条件：
$$N\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}(n-1)$$
其中N为初始距离差。当n

2时可能出现：

• 死锁情况：当N与速度差互质时无法相遇
• 稳定性：仅当n=2时保证绝对收敛

重要结论：步长差为1是唯一确保必然相遇的方案

四、环入口定位定理

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

4.1 双指针定位法

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast) {
            struct ListNode *start = head, *meet = slow;
            while(start != meet) {
                start = start->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

4.2 定理证明

说明：
H为链表的起始点，E为环入口点，M为判环时的相遇点
设
R为环的周长，L为H到E的距离，那么M到E的距离为R-X

当快慢指针相遇时，快慢指针走的路程：
fast：$$L+X+nR$$
slow: $$L+X$$
n为fast与slow相遇前在环中遍历的圈数
注意：n至少为1（要追上slow，fast至少要套一个圈）

由于fast的速度是slow的两倍
$$2(L+X)=L+X+nR$$
可得
$$L=nC-X$$

重要结论：

• 头指针走L步到达E
• 相遇点指针走(nC - X)步也到达E
• 二者必然在环入口同步相遇

五、复杂度

六、LeetCode实战

1. 141. 环形链表
2. 142. 环形链表II
   学习完本文内容，读者是不是感觉这两题是不是和喝水一样简单呢？没错，你又变强了！