题目描述
给定一个链表，判断链表中是否有环，存在环返回 true，否则返回 false
- 连续跟踪 next 指针再次到达某个节点，则链表中有环
- 你能用 O(1)（即，常量）内存解决此问题吗？
提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为环开始节点的索引，若 pos = -1，则没有环
pos 为 -1 或者链表中的一个 有效索引
pos 不作为参数进行传递，仅仅是为了标识链表的实际情况
注意：pos 只是帮助理解测试用例，并不是真正的输入值
数据结构
- 数组、指针变量
算法思维
- 遍历、双指针、快慢指针、追击
解题要点
- 链表的特点
- 快慢指针的思想以及使用
- 模型的应用：涉及"环"的问题 --> 追击问题 --> 快慢指针
解题步骤
一. Comprehend 理解题意
可以理解为"重复访问"问题，检测链表的某节点能否二次到达
- 需要一个容器记录已经访问过的节点
- 每次访问到新的节点，都与容器中的记录进行匹配，若相同则存在环
- 若匹配之后没有相同节点，则存入容器，继续访问新的节点
- 直到访问节点的next指针返回null，或者当前节点与容器的某个记录相同，操作结束
也可以理解为“追击”问题，如果存在环，跑得快的一定能追上跑得慢的
- 就像一快一慢两个运动员，如果在直道赛跑，不存在追击问题；
如果是在环道赛跑，快的绕了一圈肯定可以追上慢的 - 定义快慢两个运动员，指向链表的第一、第二个节点：
slow = head; fast = head.next; - 快运动员的步长为2，慢的为1，即fast每次移动两个节点，slow每次移动一个节点
- 若最终
fast == slow，说明存在环；若fast == null || fast.next == null，操作结束
二. Choose 选择数据结构与算法
解题方法
- 解法一：二次到达法
- 解法二：追击问题法
解法一：二次到达法
数据结构：数组（或者：链表、栈、队列）
算法思维：遍历
解法二：追击问题法
数据结构：指针变量 x 2
算法思维：遍历、双指针（快慢指针）
三. Code 编码实现基本解法
解法一：二次到达法 -- 思路分析
- 定义数组记录已访问节点：
new ListNode[10000]; - 遍历链表的每个节点，并与容器中已存放的节点依次比较：
• 相同则方法结束，返回 true
• 不同则存入最新位置，继续遍历下个节点 - 若 next 指针为 null，则方法结束，返回 false
边界问题
- 数组越界：
链表最多有一万个节点，容器不会越界；
与容器中节点进行比对，正向遍历容器，元素为 null 时终止，后续都是未使用的空间
细节问题
- 遍历链表，通过
head=head.next进行迭代
当且仅当此节点与容器某个节点相同时返回 true，其它情况都返回 false
比较相等时可以用 "=="（比较地址）
class Solution {
public boolean hasCycle(ListNode head) {
// 1.定义数组记录已访问节点
ListNode[] array = new ListNode[10000];
// 2.遍历链表的每个节点，
while(head != null) {
// 并与容器钟已存放的节点依次比较
for(int i = 0; i < array.length; i++) {
if(array[i] == head) {
return true;
}
if(array[i] == null) {
array[i] = head; // 将当前节点存放到最新位置
break; // 结束容器的遍历
}
}
head = head.next;
}
// 3.若next指针为null，则方法结束，返回false
return false;
}
}
时间复杂度：O(n2) -- 遍历数组 O(n)，每个节点都需要额外再遍历一次数组 O(n2)
空间复杂度：O(1) -- 固定长度 10000 的数组 O(1)
执行耗时：108 ms，击败了 5.26% 的Java用户
内存消耗：38.3 MB，击败了 99.89% 的Java用户
四. Consider 思考更优解
剔除无效代码，优化空间消耗
- 每个节点都需要遍历容器查找，比较耗时
- 按最大测试数据量创建容器，空间消耗巨大
寻找更好的算法思维
- 要证明某个节点是否第二次到达，可否将已遍历节点进行标记？
- 环形结构对应生活中的追击问题，可否使用“追击问题”模拟实现？
- 借鉴其它算法
五. Code 编码实现最优解
解法二：追击问题法 -- 思路分析
- 定义快慢两个指针：
slow = head; fast = head.next; - 遍历链表：
• 快指针步长为 2：fast = fast.next.next;
• 慢指针步长为 1：slow = slow.next; - 当且仅当快慢指针重合，有环，返回 true
- 快指针为 null，或其 next 指向 null，没有环，返回 false，操作结束
边界问题
- fast 和 fast.next 指针的非空判断
- slow.next 指针不需要非空判断
若有环，则始终有：slow.next != null
若无环，则 fast 或 fast.next 先为空
细节问题
- 需要注意：由于 fast 的步长为 2，因此
fast == null和fast.next == null都需要判断
class Solution {
public boolean hasCycle(ListNode head) {
//0.非空判断
if (head == null) return false;
//1.声明快慢两个指针
ListNode slow = head;
ListNode fast = head.next;
//2.利用短路特性，先判断 fast 是否为空，再判断 fast.next 是否为空
while (slow != fast && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow == fast;
}
}
时间复杂度：O(n) -- 遍历链表 O(n)
空间复杂度：O(1) -- 两个指针变量 O(1)
执行耗时：0 ms，击败了 100% 的Java用户
内存消耗：38.8 MB，击败了 88.78% 的Java用户
六. Change 变形与延伸
题目变形
- （练习）分别使用 head 和 head.next 作为链表的 快/慢 指针
- （练习）标记值法：对节点的 val 属性进行标记，赋一个超出合法范围的值
- （练习）hash 表法
延伸扩展
- 龟兔赛跑问题，追击问题
- 地球，火星与太阳连为一线的问题
