算法深潜：链表中的生死之环（LeetCode 141 142 详解）

个人主页:Marathon_X 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践《排序详解》算法思路、解题技巧与高效编程实践目录第一部分判断链表是否有环1. 问题描述2. 核心思路快慢指针法3. 数学证明重点Q1: 为什么快指针走2步慢指针走1步两者一定会相遇Q2: 如果不按照当前设定走呢还能保证相遇吗第二部分寻找环的入口1. 问题描述2. 核心思路双指针二次相遇3. 数学推导图解逻辑第三部分复杂度在链表数据结构中环是一个经典且考察频率极高的话题。这类问题通常分为两个阶段判断是否有环LeetCode 141. 环形链表。如果有环找出环的入口LeetCode 142. 环形链表 II。第一部分判断链表是否有环1. 问题描述给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回true。 否则返回false。2. 核心思路快慢指针法我们定义两个指针慢指针 (slow)一次走 1 步。快指针 (fast)一次走 2 步。算法流程初始化slow和fast都指向头节点head。只要fast和fast-next不为空循环执行slow前进 1 步。fast前进 2 步。如果fast slow说明相遇链表存在环。如果循环结束fast遇到 NULL说明无环。代码实现 (C语言)/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */boolhasCycle(structListNode*head){if(headNULL||head-nextNULL)returnfalse;//快慢指针structListNode*slowhead;structListNode*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;// 慢走1步fastfast-next-next;// 快走2步if(slowfast)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−11步/次。每一次迭代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−12。如果快指针走 4 步慢指针走 1 步相对速度是4 − 1 3 4 - 1 34−13。这意味着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进环前走的距离为Lfast在slow进环前已经绕环转了x圈距离关系分析fast走的总距离为L x*C (C - N)。slow走的距离为L。这时候就算是有个半成品的等式了现在只需要带入速度关系就可以3倍为例3L L (x1)*C - N化简后2L (x1)*C - N这时候就可以用奇偶关系判断了。关键分析如果同时存在以下两个条件N 是奇数、C 是偶数。那么根据公式偶数 (x1)*偶数 - 奇数逻辑矛盾推导(x1)*偶数的结果一定是偶数只有奇数 - 奇数 偶数才成立但等式中是偶数 - 奇数这在整数范围内不可能成立故一定追不上。结论如果步同时存在N 是奇数且C 是偶数的情况永远追不上的条件不成立因此快慢指针一定能相遇。相遇情况总结当N 是偶数第一轮追击就能相遇当N 是奇数、C 是偶数一定追不上。其他情况都会在后面几轮追上。第二部分寻找环的入口1. 问题描述给定一个链表的头节点head返回链表开始入环的第一个节点。 如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。2. 核心思路双指针二次相遇第一次相遇使用快慢指针判断是否有环若有环记录相遇点。寻找入口让一个指针从头节点 (Head)出发。让另一个指针从相遇点 (Meeting Node)出发。两个指针都每次走 1 步。它们最终会在环入口 (Entry Node)相遇。代码实现 (C语言)structListNode*detectCycle(structListNode*head){structListNode*slowhead;structListNode*fasthead;// 步骤一判断是否有环while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;if(slowfast){// 步骤二发现环寻找入口// 1. 定义两个指针index1在头index2在相遇点structListNode*index1head;structListNode*index2slow;// 2. 两人每次都走一步直到相遇while(index1!index2){index1index1-next;index2index2-next;}// 3. 相遇点即为环入口returnindex1;}}returnNULL;}3. 数学推导图解逻辑设L LL 头节点到环入口的距离。C CC 环的长度。N NN 环入口到相遇点的距离沿运行方向。相遇时慢指针在环内走了N NN的距离。推导过程慢指针slow走的距离S s l o w L N S_{slow} L NSslow​LN(注意通常慢指针在入环第一圈内就会被追上)快指针fast走的距离S f a s t L N n C S_{fast} L N nCSfast​LNnC(n nn是快指针在环内绕的圈数且n ≥ 1 n \ge 1n≥1)速度关系快指针速度是慢指针的 2 倍。2 × ( L N ) L N n C 2 \times (L N) L N nC2×(LN)LNnC化简公式2 L 2 N L N n C 2L 2N L N nC2L2NLNnCL N n C L N nCLNnCL n C − N L nC - NLnC−N关键变换为了直观理解我们将n C nCnC拆解为( n − 1 ) C C (n-1)C C(n−1)CCL ( 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等几个指针变量没有使用额外的数据结构。