【初探数据结构】带环链表：原理、判断与数学证明-阿南达文事网

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

一、何为带环链表

1.1 带环链表的定义

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

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

1.2 典型示例

#mermaid-svg-ToVahgTiNqcUf7q1 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .error-icon{fill:#552222;}#mermaid-svg-ToVahgTiNqcUf7q1 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ToVahgTiNqcUf7q1 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ToVahgTiNqcUf7q1 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ToVahgTiNqcUf7q1 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ToVahgTiNqcUf7q1 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ToVahgTiNqcUf7q1 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ToVahgTiNqcUf7q1 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ToVahgTiNqcUf7q1 .marker.cross{stroke:#333333;}#mermaid-svg-ToVahgTiNqcUf7q1 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ToVahgTiNqcUf7q1 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .cluster-label text{fill:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .cluster-label span{color:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .label text,#mermaid-svg-ToVahgTiNqcUf7q1 span{fill:#333;color:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .node rect,#mermaid-svg-ToVahgTiNqcUf7q1 .node circle,#mermaid-svg-ToVahgTiNqcUf7q1 .node ellipse,#mermaid-svg-ToVahgTiNqcUf7q1 .node polygon,#mermaid-svg-ToVahgTiNqcUf7q1 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ToVahgTiNqcUf7q1 .node .label{text-align:center;}#mermaid-svg-ToVahgTiNqcUf7q1 .node.clickable{cursor:pointer;}#mermaid-svg-ToVahgTiNqcUf7q1 .arrowheadPath{fill:#333333;}#mermaid-svg-ToVahgTiNqcUf7q1 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ToVahgTiNqcUf7q1 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ToVahgTiNqcUf7q1 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ToVahgTiNqcUf7q1 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ToVahgTiNqcUf7q1 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ToVahgTiNqcUf7q1 .cluster text{fill:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 .cluster span{color:#333;}#mermaid-svg-ToVahgTiNqcUf7q1 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ToVahgTiNqcUf7q1 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}

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

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

2.1 快慢指针实现

代码语言：javascript代码运行次数：0运行复制

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 ->……-> 2 -> 1 -> 0

初始条件：

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

运动方程：

\begin{cases} v_{\text{fast}} = 2v_{\text{slow}} \\ S_{\text{fast}} = L + X + nC \\ S_{\text{slow}} = L + X \end{cases}

推导结论：

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。

分情况讨论：

N为偶数 fast和slow的距离：

N -> N-2 -> N-4 ->……-> 2 -> 1 -> 0

可以追上

N为奇数

代码语言：javascript代码运行次数：0运行复制

 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 \mod (n-1)

其中N为初始距离差。当n

2时可能出现：

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

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

四、环入口定位定理

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

4.1 双指针定位法

代码语言：javascript代码运行次数：0运行复制

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
二者必然在环入口同步相遇

五、复杂度

算法	时间复杂度	空间复杂度	稳定性
Floyd判圈	O(n)	O(1)	稳定
哈希表检测	O(n)	O(n)	通用

六、LeetCode实战

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-03-10，如有侵权请联系 cloudcommunity@tencent 删除链表数学原理指针数据结构

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