题目描述
给定一个链表，返回链表开始入环的第一个节点
如果链表无环，则返回 null
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）
如果 pos 是 -1，则在该链表中没有环
注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中
说明：不允许修改给定的链表
进阶：你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围 [0, 10^4] 内
- -10^5<= Node.val <= 10^5
- pos 的值为 -1 或者链表中的一个有效索引
数据结构
- 链表（题目自带）、指针变量
算法思维
- 遍历、快慢指针、逆推、数学思维：环的同步
解题要点
- 环长度的计算
- 数学思维的运用：环的同步
相同速度下，领先一个环长的指针将和从 head 出发的指针在环的首节点相遇，并从此进入同步
解题思路
一. Comprehend 理解题意
- 需要判断链表中是否有环
- 需要找到环的第一个节点
- 不能破坏或改变环的结构和数据
可以使用“追击问题”的思路来判断环的存在，但如何找到环的第一个节点呢？
首先想到的肯定是给链表加一个 int 类型的属性，相当于索引或者编号，但题目明确要求了“不能破坏或改变环的结构和数据”，所以这种方法肯定是不行的
题意是希望我们使用遍历的方式，不改变链表，光靠“看”和“算”，找到环的首节点，而一旦涉及到“算”，我们就必须使用数学方法来解决问题
二. Choose 选择数据结构与算法
解法一：一快两慢指针法
- 数据结构：指针变量
- 算法思维：遍历、快慢指针、逆推、数学思维：环的同步
(一) 环首节点的定位
要定位到链表中的某个节点，需要特定的判断条件
要创造判断条件，我想到如下的两个方式：
- 索引
虽然题目中不允许给链表添加属性，但是我们可以使用一个 int 类型的变量 n，实时记录当前遍历的位置。
如果我们通过某个数学公式，计算出了环的首节点在链表中位置，就可以通过索引来控制遍历的步数，从而使用条件i == n进行定位：
ListNode li = head;
for (int i=0; i<n i++) {
li = li.next;
}
return li;
很可惜，经过各种尝试，仍然没能找到首节点位置与相遇位置之间的关系，即无法通过快慢指针相遇的位置计算出首节点索引，只能再想其他办法
- 相遇
如果有两个指针 a 和 b 恰好在环的首节点相遇，这时就可以使用条件a == b进行定位：
while (a != b) {...}
return a;
那么，该如何控制两个指针，让它们恰好在环的首节点相遇呢？
- 从 环形链表 I 题中可知，快慢指针并不一定会相遇在环的首节点，因此使用快慢指针肯定是不行的，故此考虑使用两个速度均为 1个步长 的慢指针，方便控制
这里可以使用 反推 / 逆推 的方法，去“凑”相遇条件。
想象一个环形的跑道（如上图），两个小人若要在起点相遇，则需要满足两个条件：
- 两个小人速度相同
- 黄色小人刚好领先蓝色小人一圈的距离
于是得出结论：相同速度下，领先一个环长的指针将和从 head 出发的指针在环的首节点相遇，并从此进入同步
(二) 环长的计算
明晰了相遇条件（步长相等 + 领先一个环长），接下来就是如何计算环的长度了，环长的计算比较容易：
- 定义快慢两个指针：
slow：从 head 开始，逐个节点遍历链表（步长为 1）
fast：从 head.next 开始，跨一个节点遍历链表（步长为 2） - slow 和 fast 相遇时走过的 “步数n” 是相同的，因此 fast 走过的距离是 2n，slow 走过的距离是 n
- 由相遇条件，二者相遇时 fast 比 slow 多走了一圈，即有：
2n + 1 = n + 环长 --> 环长 = 2n-n+1 = n+1
至此，所有的准备工作都已经完毕，可以开始实现思路了！！
三. Code 编码实现基本解法
实现步骤：
- 声明一个用来记录步数的变量
- 声明快慢两个指针
- 以不同的步长遍历链表
- 先判断是否有环
- 如果有环，计算环的长度 = n+1
- 声明一个新的慢指针，从 head 开始遍历
- slow 前进一步，此时 slow 领先了 slow2 一个 cycLen
- 以一倍步长遍历链表，直到 slow 和 slow2 相遇
- 相遇的位置即为环的第一个节点
代码如下：
public class Solution {
public ListNode detectCycle(ListNode head) {
//0.非空判断
if (head == null) return null;
//1.声明一个用来记录步数的变量
int n = 0;
//2.声明快慢两个指针
ListNode slow = head;
ListNode fast = head.next;
//3.以不同的步长遍历链表
while (fast != null && fast.next != null) {
//4.先判断是否有环
if (slow == fast) {
//5.如果有环，计算环的长度 = 1 + fast 路程 - slow 路程 = 1 + 2n - n = n+1
int cycLen = n+1; //这一步只是方便理解，可以省略
//6.声明一个新的慢指针，从 head 开始遍历
ListNode slow2 = head;
//7.slow 前进一步，此时 slow 领先了 slow2 一个 cycLen
slow = slow.next;
//8.以一倍步长遍历链表，直到 slow 和 slow2 相遇
while (slow != slow2) {
slow = slow.next;
slow2 = slow2.next;
}
//9.相遇的位置即为环的第一个节点
return slow;
}
slow = slow.next;
fast = fast.next.next;
n++;
}
return null;
}
}
执行耗时：0 ms,击败了 100.00% 的Java用户
内存消耗：38.2 MB，击败了 97.56% 的Java用户
时间复杂度：O(n) -- 链表的遍历 O(n)
空间复杂度：O(1) -- 3个指针变量的内存空间 O(n)
四. Consider 思考更优解
=== 暂无 ===
五. Code 编码实现最优解
=== 暂无 ===
六. Change 变形与延伸
=== 待续 ===
网友评论