企业官网建设流程全解析

环形链表

题目

环型链表

解析

分析可知：环有大有小

判断是否有环的办法：使用快慢指针

快指针走两步，慢指针走一步
当快慢指针相遇时，说明链表有环

得到程序代码

typedefstructListNodeListNode;boolhasCycle(structListNode*head){ListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow)returntrue;}returnfalse;}

环形链表II

题目

环形链表II
题目要求：返回环的第一个节点，无环返回NULL

解析

两个步骤：1. 判断是否有环 2. 有环返回环的第一个节点

对于步骤1，前面已经解答

对于步骤2，解析如下：
快慢指针第一次相遇的节点为meet
一个指针从链表的头节点head开始走，一个指针从meet节点开始走，两个指针相遇处就是环的入口处（稍后证明）

得到本题代码：

// 1. 判断是否存在环 2. 返回环的入口节点typedefstructListNodeListNode;structListNode*detectCycle(structListNode*head){// 1. 快慢指针判断是否存在环// fast = 2*slowListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;// 快慢指针相遇, 存在环if(slow==fast){// 2. 返回环的入口节点ListNode*meet=slow;ListNode*pcur=head;while(meet!=pcur){meet=meet->next;pcur=pcur->next;}returnmeet;}}// 快指针访问到NULL,不存在环returnNULL;}

要点

在一定有环存在的情况下，存在两个疑问：

1. 为什么两个指针一定会相遇，有没有可能会错过，永远追不上？请证明
2. 如果fast改为一次走 3 / 4 / 5 …… n 步，还一定能追上吗？为什么？请证明

问题一：一定能相遇吗？

为什么一定会相遇，有没有可能会错过，永远追不上？为什么？请证明

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

fast 每次走两步，slow 每次走一步
每追击一次，fast 与 slow 之间的距离就缩短 1

fast 与 slow 之间的距离变化为： N N - 1 N - 2 N - 3 …… 2 1 0

当 fast 与 slow 之间的距离为 0 时，就是追上了

问题二：如果fast走其他步能追上吗？

如果 slow 走一步，fast 走 3 / 4 / 5 ……n 步，还一定能追上吗？请证明
（此处只证明 fast 走 3 步时，其余方法一致）

假设：

• slow进入环中时，fast与slow的距离为N
• 环的周长为C
• 从链表头节点phead开始，到环节点的距离为L
  

fast 与 slow 之间的距离变化为： N为偶数 N为奇数 N N N - 2 N - 2 N - 4 N - 4 N - 6 N - 6 …… …… 4 3 2 1 0 -1

当fast与slow之间的距离为0时，表示追上了
当fast与slow之间的距离为-1时，表明错过了，开始新的一轮追击，此时fast与slow之间的距离为C-1

此时fast与slow之间的距离为C-1 fast与slow之间的距离变化如下： C为奇数 C为偶数 C - 1 C - 1 C - 3 C - 3 C - 5 C - 5 …… …… 4 3 2 1 0 -1

当fast与slow之间的距离为0时，表示追上了
当fast与slow之间的距离为-1时，表明错过了，开始重复追击，此时fast与slow之间的距离为C-1，将循环追击，永远追不上

总结：
当 N 为偶数时，第一轮追击就追上了
当 N 为奇数时，第一轮追击会错过，fast 与 slow 之间的距离变成 C - 1

• 如果 C - 1 为偶数：第二轮追上
• 如果 C - 1 为奇数：永远追不上

如果同时存在 N 为奇数 且 C 为偶数，那么就永远追不上

问：存在这种情况吗？

slow 进入环中时，fast 与 slow 的距离为 N
环的周长为 C
从链表头节点 phead 开始，到环节点的距离为 L

假设 slow 进环时，fast 已经在环内转了 x 圈

slow 进环时： slow 走的距离：L fast 走的距离： L+x*C+C-N 已知：fast 走的距离时 slow 的三倍 3L = L+x*C+C-N 化简得：2L = (x+1)*C-N

已知永远追不上的条件为：1. N 为奇数 2. C 为偶数
所以代入 2L = (x+1)*C-N 中得

偶数 = (x+1)*偶数 - 奇数 偶数*任何数都是偶数 偶数-奇数 = 奇数 再次化简为：偶数 = 偶数 - 奇数

所以等式两边不相等！N 为奇数和 C 为偶数的情况不能同时存在！永远追不上的情况不存在！
N 是奇数时，C 为奇数
N 是偶数时，C 为偶数

结论：一定追得上
N 为偶数时，第一轮就追上了
N 为奇数时，第二轮才能追上(第一轮错过，开始第二轮追击，第二轮追击距离为C-1，C-1为偶数，第二轮追上)

问题三：如何找到环的第一个节点？

一个指针从链表头节点phead处开始走，一个指针从快慢指针第一次相遇的节点meet开始走，两个指针相遇的节点，为什么就是环的入口点处？请证明

假设快慢指针相遇时：

1. 从链表头节点到环的入口点的距离为 L
2. 环的周长为 C
3. 快指针 fast 已经在环内转了 x 圈
4. 快慢指针相遇点到环的入口点的距离为 N

注意： 慢指针slow不可能在环中走超过1圈
原因： 慢指针入环时，快慢指针之间只有<环的初始距离，当慢指针走满一圈时，fast已经在环内走了两圈，早就已经超过了初始距离

注意：快指针在环内转了 x 圈，x 必然 ≥ 1，即快指针至少在环内走了 1 圈
原因：慢指针进入环时，快指针已经进入环了，当快指针追上慢指针时，最少要在环内走一圈

slow 走的距离: L + N fast 走的距离: L + x*C + N 已知: fast = 2*slow 2*(L + N) = L + x*C + N 化简得: L = x*C - N --> L = (x - 1)*C + C - N (x - 1)*C 即在环内转了 x-1 圈 C - N 正好是从 meet 节点到环的入口处的距离

由此可得：
当从头节点phead开始走的指针，走到环的入口处时，从meet处开始走的指针正好绕道环的入口处