尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

算法深潜:链表中的生死之环(LeetCode 141 142 详解)

算法深潜:链表中的生死之环(LeetCode 141  142 详解)
📅 发布时间:2026/7/14 18:15:39


🏠 个人主页:Marathon_X

📚 个人专栏:

专栏名称专栏主题简述
《C语言》C语言基础、语法解析与实战应用
《数据结构》线性表、树、图等核心数据结构详解
《题解思维》算法思路、解题技巧与高效编程实践
《排序详解》算法思路、解题技巧与高效编程实践


目录

  • 第一部分:判断链表是否有环
    • 1. 问题描述
    • 2. 核心思路:快慢指针法
    • 3. 数学证明(重点)
      • Q1: 为什么快指针走2步,慢指针走1步,两者一定会相遇?
      • Q2: 如果不按照当前设定走呢?还能保证相遇吗?
  • 第二部分:寻找环的入口
    • 1. 问题描述
    • 2. 核心思路:双指针二次相遇
    • 3. 数学推导(图解逻辑)
  • 第三部分:复杂度

在链表数据结构中,"环"是一个经典且考察频率极高的话题。这类问题通常分为两个阶段:

  1. 判断是否有环(LeetCode 141. 环形链表)。
  2. 如果有环,找出环的入口(LeetCode 142. 环形链表 II)。

第一部分:判断链表是否有环

1. 问题描述

给你一个链表的头节点head,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回true。 否则,返回false。

2. 核心思路:快慢指针法

我们定义两个指针:

  • 慢指针 (slow):一次走 1 步。
  • 快指针 (fast):一次走 2 步。

算法流程:

  1. 初始化slow和fast都指向头节点head。
  2. 只要fast和fast->next不为空,循环执行:
    • slow前进 1 步。
    • fast前进 2 步。
    • 如果fast == slow,说明相遇,链表存在环。
  3. 如果循环结束(fast遇到 NULL),说明无环。

代码实现 (C语言)

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */boolhasCycle(structListNode*head){if(head==NULL||head->next==NULL)returnfalse;//快慢指针structListNode*slow=head;structListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;// 慢走1步fast=fast->next->next;// 快走2步if(slow==fast)returntrue;// 相遇,有环}returnfalse;// 走到尽头,无环}

3. 数学证明(重点)

Q1: 为什么快指针走2步,慢指针走1步,两者一定会相遇?

证明(相对速度法):

我们假设在慢指针刚刚进入环的那一时刻,快指针开始追,这时候不知道快指针已经走多少圈了,就假设在此时我图中标记的位置。

下来我们为了证明是否一定能追上,定义几个距离,看看最后是否能推出一个数学表达式。

  • 假设从初始位置到刚进入环的距离是L。
  • 假设slow进入环时,fast追上slow的距离为N NN(沿链表运行方向)。
  • 假设链表环长度为C。


现在fast速度是slow的两倍,也就是每次多走1,也就是在N这个距离中,每次距离会少1,直至为0,一定会追上。
N → N − 1 → N − 2 → . . . → 1 → 0 N \rightarrow N-1 \rightarrow N-2 \rightarrow ... \rightarrow 1 \rightarrow 0N→N−1→N−2→...→1→0
证明总结:

  • 当slow进入环之后,fast已经在环内了。
  • 假设slow进入环时,fast领先slow的距离为N NN(沿链表运行方向)。
  • 我们将slow看作静止,那么fast相对于slow的移动速度是2 − 1 = 1 2 - 1 = 12−1=1步/次。
  • 每一次迭代,fast都会把它和slow之间的距离缩短 1。
  • 距离变化过程:N , N − 1 , N − 2 , . . . , 1 , 0 N, N-1, N-2, ..., 1, 0N,N−1,N−2,...,1,0。

结论:因为距离每次减 1,必然会减到 0(相遇),绝对不会跳过去。

Q2: 如果不按照当前设定走呢?还能保证相遇吗?

这是一个非常好的进阶面试题。

分析:

  • 在刚才的分析中,我们是找到了相对速度,每次会少一步。
    • 如果快指针走 3 步,慢指针走 1 步,相对速度是3 − 1 = 2 3 - 1 = 23−1=2。
    • 如果快指针走 4 步,慢指针走 1 步,相对速度是4 − 1 = 3 4 - 1 = 34−1=3。
  • 这意味着fast每次把距离缩短一个相对速度的距离。
  • 还是按照上面的假设进行推演,得到每次相距的距离。


这里为什么有这么多情况呢?因为不知道N到底有多大,它有可能是奇数、偶数、0,都有可能。
所以需要对每一个结果进行讨论,当最后距离为0的时候,显然已经追上了,那么-1代表什么意思呢?很显然,代表这时候已经进入下一轮追击了,且快指针就在慢指针前面一个位置。那个-2也是一样的道理。

那我们之前设的圆环长度还一直没用呢,这时候就派上用场了。-1、-2,那这时候相对距离就是C-1、C-2。

走三步的情况下:

  • N为偶数,第一轮追上。
  • N为奇数,第一轮错过,看环长度。
    • C − 1 C-1C−1为奇数,那么永远追不上。
    • C − 1 C-1C−1为偶数,那么下一轮就追上了。

走四步的情况:

走四步就不能看奇偶了,而是是不是三的倍数,因为每次距离会少三,所以三的倍数一定会追上。

  • N % 3 = 0,首轮就追上。
  • N % 3 = 1,首轮错过,看环长。
    • (C-1) % 3 = 0,下一轮追上。
    • (C-1) % 3 = 1,永远追不上。
    • (C-1) % 3 = 2,看下述情况。
  • N % 3 = 2`,首轮错过,看环长。
    • (C-1) % 3 = 0,下一轮追上。
    • (C-1) % 3 = 1,看上述情况。
    • (C-1) % 3 = 2,永远追不上。

那么有没有一个稍微通用的结论呢?尝试一下

  • 设慢指针slow进环时,快指针fast与slow的距离为N
  • 设slow进环前走的距离为:L
  • fast在slow进环前已经绕环转了x圈

距离关系分析

  • fast走的总距离为:L + x*C + (C - N)。
  • slow走的距离为:L。

这时候就算是有个半成品的等式了,现在只需要带入速度关系就可,以3倍为例:

  • 3L = L + (x+1)*C - N
  • 化简后:2L = (x+1)*C - N,这时候就可以用奇偶关系判断了。

关键分析:如果同时存在以下两个条件:N 是奇数、C 是偶数。

那么根据公式:偶数 = (x+1)*偶数 - 奇数

逻辑矛盾推导

  • (x+1)*偶数的结果一定是偶数
  • 只有奇数 - 奇数 = 偶数才成立
  • 但等式中是偶数 - 奇数,这在整数范围内不可能成立,故一定追不上。

结论:如果步同时存在N 是奇数且C 是偶数的情况,永远追不上的条件不成立,因此快慢指针一定能相遇。

相遇情况总结

  1. 当N 是偶数:第一轮追击就能相遇
  2. 当N 是奇数、C 是偶数,一定追不上。
  3. 其他情况都会在后面几轮追上。

第二部分:寻找环的入口

1. 问题描述

给定一个链表的头节点head,返回链表开始入环的第一个节点。 如果链表无环,则返回null。
如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。如果pos是-1,则在该链表中没有环。注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。

2. 核心思路:双指针二次相遇

  1. 第一次相遇:使用快慢指针判断是否有环,若有环,记录相遇点。
  2. 寻找入口:
    • 让一个指针从头节点 (Head)出发。
    • 让另一个指针从相遇点 (Meeting Node)出发。
    • 两个指针都每次走 1 步。
    • 它们最终会在环入口 (Entry Node)相遇。

代码实现 (C语言)

structListNode*detectCycle(structListNode*head){structListNode*slow=head;structListNode*fast=head;// 步骤一:判断是否有环while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){// 步骤二:发现环,寻找入口// 1. 定义两个指针,index1在头,index2在相遇点structListNode*index1=head;structListNode*index2=slow;// 2. 两人每次都走一步,直到相遇while(index1!=index2){index1=index1->next;index2=index2->next;}// 3. 相遇点即为环入口returnindex1;}}returnNULL;}

3. 数学推导(图解逻辑)

设:

  • L LL= 头节点到环入口的距离。
  • C CC= 环的长度。
  • N NN= 环入口到相遇点的距离(沿运行方向)。
  • 相遇时,慢指针在环内走了N NN的距离。

推导过程:

  1. 慢指针slow走的距离:S s l o w = L + N S_{slow} = L + NSslow​=L+N
    (注意:通常慢指针在入环第一圈内就会被追上)

  2. 快指针fast走的距离:S f a s t = L + N + n C S_{fast} = L + N + nCSfast​=L+N+nC
    (n nn是快指针在环内绕的圈数,且n ≥ 1 n \ge 1n≥1)

  3. 速度关系:快指针速度是慢指针的 2 倍。
    2 × ( L + N ) = L + N + n C 2 \times (L + N) = L + N + nC2×(L+N)=L+N+nC

  4. 化简公式:
    2 L + 2 N = L + N + n C 2L + 2N = L + N + nC2L+2N=L+N+nC
    L + N = n C L + N = nCL+N=nC
    L = n C − N L = nC - NL=nC−N

  5. 关键变换:
    为了直观理解,我们将n C nCnC拆解为( n − 1 ) C + C (n-1)C + C(n−1)C+C:
    L = ( n − 1 ) C + ( C − N ) L = (n-1)C + (C - N)L=(n−1)C+(C−N)

公式含义解析:

  • L LL是从头走到入口的距离。
  • ( C − N ) (C - N)(C−N)恰好是从相遇点继续往前走,回到环入口的距离。
  • ( n − 1 ) C (n-1)C(n−1)C表示在环里转了n − 1 n-1n−1圈(这对最终位置没有影响)。

结论:从头节点出发走L LL步,和从相遇点出发走L LL步(实际上是转几圈后走了C − N C-NC−N),会同时到达环入口。

第三部分:复杂度

  • 时间复杂度:O ( N ) O(N)O(N)。
    • 判断有环时,快慢指针在环内移动次数不会超过环的长度,总步数与节点数N NN线性相关。
    • 寻找入口时,同样是线性遍历。
  • 空间复杂度:O ( 1 ) O(1)O(1)。
    • 只使用了slow,fast等几个指针变量,没有使用额外的数据结构。

相关新闻

  • AI 编程普及,初学者还要不要学习基础语法?
  • B站视频下载终极指南:5分钟掌握跨平台免费下载工具BilibiliDown
  • 综合实力最强的国际EMBA怎么选?2026避坑选购推荐攻略

最新新闻

  • 深度学习经典教材《Deep Learning》核心解析与实践指南
  • YOLOv8的C2f模块源码全解析:为什么它比C3更高效?
  • 企业级 AI 应用工程实战(八):向量数据库选型与语义检索实现
  • 人工智能的现在与未来:从技术演进到产业融合的深度剖析
  • 计算机毕业设计之基于SSM框架的流浪狗收容管理系统
  • Linux系统xz命令进阶实战:从基础压缩到高效归档与性能调优

日新闻

  • AWS SSM安全运维实践:零公网暴露的合规远程开发方案
  • Tableau 2024.1 图表选择指南:5种业务场景与最佳图表类型匹配
  • dsPIC33FJ与CMT-8540S-SMT在嵌入式音频处理中的高效应用

周新闻

  • IX9104 PCIe5.0 高速交换芯片@ACP#完整规格 + 应用场景总结
  • Unity游戏集成Coze智能体:实现NPC智能对话与知识库联动
  • SAP EPIC 建行回单查询:从标准类CL_EPIC_EXAMPLE_CN_CCB_GHTD到Z类的5处关键修改

月新闻

  • 2026年6月公司网站搭建最新热门渠道测评:四大低成本/零代码平台对比+避坑
  • 【Linux】Linux arm 编译QT程序,出现expected “}“报错
  • 【MATLAB例程】四基站二维AOA定位与距离辅助增强对比仿真。基于角度观测和测距修正的固定目标平面定位精度分析

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号