题目一 环形链表
给你一个链表的头节点 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, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
解法
解法一 Set保存ListNode
将遍历过的ListNode存入HashSet，出现重复的就说明有环
public class Solution {
public boolean hasCycle(ListNode head) {
// 在HashMap中保存ListNode，key是ListNode， value是下标
Set<ListNode> set = new HashSet<>();
ListNode currentNode = head;
while (currentNode != null) {
if (set.contains(currentNode)) return true;
set.add(currentNode);
currentNode = currentNode.next;
}
return false;
}
}用了额外的空间，空间复杂度为O(N)
解法二 在原链表上做标记
看到条件-105 <= Node.val <= 105
可以取巧，将遍历过的节点的值标记为100001作为标记
public class Solution {
public boolean hasCycle(ListNode head) {
// 将遍历过的val变为100001作为标记
ListNode currentNode = head;
while (currentNode != null) {
if (currentNode.val == 100001) return true;
currentNode.val = 100001;
currentNode = currentNode.next;
}
return false;
}
}对原本的链表是侵入性的，只是为最佳时间复杂度设计的
解法三 快慢指针 – Floyd判圈法
Floyd判圈法 又称龟兔赛跑算法
直观的解释是，在环形跑道赛跑时，跑的快的会和跑的慢的一定会相遇，也就是被套圈了。
因此，如果快慢指针相遇了就说明是环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slowNode = head, fastNode = head.next;
while (fastNode.next != null && fastNode.next.next != null) {
if (fastNode == slowNode) return true;
slowNode = slowNode.next;
fastNode = fastNode.next.next;
}
return false;
}
}该解法为本题最优雅解法，对原本链表没有侵入性
时间复杂度O(N) 空间复杂度O(1)
小结
本题提供了判圈的优雅思路：Floyd判圈法，加深了对快满指针应用场景的理解！
题目二 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
解法
本题与第一题的不同在于要求返回开始入环的第一个节点
因此解法一 Set保存ListNode当然是可行的，但是空间复杂度在O(N)
Floyd判圈法怎么知道是哪一个节点入环呢？
考虑通过第二次相遇和第一次相遇中间slow走过的路径是环的长度
因为我们是通过快慢指针相遇来判断有环的，自然而然可以想到一个思路——只要快慢指针直接在入环的时候相遇，就可以直接返回了。
假设:
- 快指针速度为2，在0处出发
- 慢指针速度为1，在0处出发
- 快慢指针在第t步相遇
此时满足 2t = t + 环的长度，得到环的长度为 t；
让先后指针以相同速度重新出发，但是先指针提前走过环的长度，此时两指针相遇处就是入环处（因为环的长度 + 环前面的长度 = 固定的总长度）
/**
* 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) {
if (head == null || head.next == null) return null;
ListNode slowNode = head, fastNode = head;
int lengthCycle = 0;
// 快慢指针得到环的长度
while (fastNode != slowNode || lengthCycle == 0) {
if (fastNode.next == null || fastNode.next.next == null)
return null;
fastNode = fastNode.next.next;
slowNode = slowNode.next;
lengthCycle++;
}
slowNode = head;
fastNode = head;
// 先后指针
for (int i = 0; i < lengthCycle; i++) fastNode = fastNode.next;
while (fastNode != slowNode) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
return slowNode;
}
}
小结二
本题同样是Floyd判圈法的应用，注意到用快慢指针相遇的时机来得到环的长度，通过这个长度来对环开头进行查找。