141题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 10^4]
- $-10^5 <= Node.val <= 10^5$
- pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
分析
- 哈希表存储，索引
- 快慢指针相遇
哈希表存储，索引
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (!seen.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}
快慢指针相遇
快指针两步走，慢指针一步走。
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head; // 乌龟和兔子同时从起点出发
while (fast != null && fast.next != null) {
slow = slow.next; // 乌龟走一步
fast = fast.next.next; // 兔子走两步
if (fast == slow) // 兔子追上乌龟（套圈），说明有环
return true;
}
return false; // 访问到了链表末尾，无环
}
}
142 题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
分析
要返回环的入口节点
哈希表
第一个重复的节点
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
if (visited.contains(pos)) {
return pos;
} else {
visited.add(pos);
}
pos = pos.next;
}
return null;
}
}
双指针遍历
设链表非环部分长度为a，环的长度为b
第一次相遇，必定在环内：
设慢指针走了c步，则慢指针距离环的入口 a-c 个节点。
则快指针走了 2*c 步：2 * c = c + k * b => c = k * b
- 令 a-c = x, 则 a + x = c => a + x = k * b
深奥版本
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {// 第一次相遇
while (slow != head) {// slow、head相遇
slow = slow.next;
head = head.next;
}
return slow;
}
}
return null;
}
}
易懂版本——问题转换为求链表的倒数第b个节点（链表中有环，环的长度是b）
快慢双指针无脑相遇
求环长len
走环的长度len
头指针、慢指针 双指针前进，相遇便是倒数b个节点（环的入口）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
// 无脑相遇
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) return null;
// 相遇了,算出环的长度 b
int len = 1;
ListNode tmp = fast;
while (tmp.next != fast) {
tmp = tmp.next;
len++;
}
// slow 从头开始走环的长度 b
slow = head;
for (int i = 0;i < len;i++) {
slow = slow.next;
}
// fast 从头开始走，走a步，slow必定走到了环入口
// 公式：a+b = b+a(因为有环，所以b+a必定是到达环的入口)
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
