1. 判断链表有环 (141-易)
题目描述：给定一个链表，判断链表中是否有环，不能使用额外空间。
注意：我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 ：
输入：head = [3,2,0,-4], pos = 1（标识链表情况）
输出：true
解释：链表中有一个环，其尾部连接到第二个节点
思路：使用快慢指针，快指针每次走两步，慢指针每次走一步，最终快慢指针相遇，即有环。为什么呢？如果有环，快慢指针一定会先后进入环，所以必定在环中的某个位置相遇。第一次相遇直接返回true。
ps：针对快慢指针，如果慢指针每次走m步，快指针每次走n步，只要m≠n，好像都能通过
另外说一下其他的实现思路：
（1）hashset存储链表节点，遍历链表，依次加入节点，当加入失败，即存在环。
（2）反转链表：如果存在环，那么反转前后头结点一定相同，因为环之前的链表已经反转。
（3）删除链表节点：即让节点的next节点指向自己，如果存在环，最后会出现head = head.next。
代码：
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode l1 = head, l2 = head;
while (l2 != null && l2.next != null) {
l1 = l1.next;
l2 = l2.next.next;
if (l1 == l2) return true; //快慢指针第一次相遇
}
return false;
}
ps：如果快指针走三步或者四步呢？可能相遇，快指针走两步，相对于慢指针每次迫近一步，一定相遇；如果快指针走三步或者四步，即相对慢指针每次迫近两步或三步，可能略过。
2.环的长度
思路：前面已经判断该链表中有环，即l1和l2必定在环中某个节点相遇。
这里记录这个节点，用另一个指针p遍历该链表，记录经过节点数，当重新回到该节点，就得到了环的长度。简单说，让这个p指针从这个交点开始，绕着环走一圈，重新回到这个交点。
代码：
private ListNode crossNode;
public int cycleLength(ListNode head) {
if (!hasCycle(head)) return 0;
ListNode p = crossNode;
int len = 0;
while (p.next == crossNode) {
len++;
p = p.next;
}
return len;
}
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode l1 = head, l2 = head;
while (l2 != null && l2.next != null) {
l1 = l1.next;
l2 = l2.next.next;
if (l1 == l2) {
crossNode = l1; //记录相遇节点
return true;
}
}
return false;
}
3.环的入口节点（142-易）
思路：hash表简单，遍历链表，当set中包含该节点，直接返回（否则加入集合）。快慢指针推导如下：
第一次相遇时，设快指针走了f，慢指针走s，环长为r，这里n的取值为（1...n）则有：
1. f = 2s
2. f = s + nr
推出：s = nr
假设整个链表的长度是L，入口和相遇点的距离是x，起点到入口点的距离是a，则有：
3. a + x = s = nr
4. a + x = (n - 1) * r + r = (n - 1) * r + (L - a)
5. a = (n - 1) * r + (L - a - x)
这里n取1，L - a - x：慢指针走完整个链表（即环的入口节点），上述过程大家可以自行画图。
从fast节点（每次一步）从head开始，和slow指针一起走，再次相遇时刚好就是环的入口节点。
代码：
public ListNode detectCycle(ListNode head) {
ListNode l1 = head, l2 = head;
while (true) {
if (l2 == null || l2.next == null) return null; //一定没有环
l1 = l1.next;
l2 = l2.next.next;
if (l1 == l2) break;
}
l2 = head; // 复用l2指针，从头遍历链表
while (l1 != l2) {
l1 = l1.next;
l2 = l2.next;
}
return l2;
}
拓展：4. 寻找重复数（287-易）
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），假设只有一个重复的整数，找出这个重复的数（可重复多次）。要求：线性时间复杂度，不使用额外空间。
示例 :
输入: [1,3,4,2,2]
输出: 2
实现思路：同样的本题可以使用hash表实现和值域的二分查找。代码如下:
class Solution {
// hash表，空间和时间复杂度O(n)
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (set.contains(i)) {
return i;
}
set.add(i);
}
return -1;
}
// 值域的二分查找，时间复杂度O(nlogn)
public int findDuplicate(int[] nums) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
int cnt = 0;
for (int i = 0; i < nums.length; ++i) {
// 统计集合中小于mid的个数
if (nums[i] <= mid) {
cnt++;
}
}
// 小于等于mid的个数大于mid，说明mid选大了
if (cnt > mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
由于数组下标和数组内容的特殊对应性，建立下标与对应数值的映射，将这些映射连接起来。
这样就可以将这个题目给的特殊的数组当作一个链表来看，数组的下标就是指向元素的指针，把数组的元素也看作指针。如 0 是指针，指向 nums[0]，而 nums[0] 也是指针，指向 nums[nums[0]].
这里的寻找重复数字即上边寻找带环链表入口的问题！注意两点：
- 由于含有唯一重复数字，即只有一个环（不考虑后续）
- 下标和数组元素均作为链表元素出现
代码
public int findDuplicate(int[] nums) {
int l1 = 0, l2 = 0;
while (true) {
l1 = nums[l1];
l2 = nums[nums[l2]];
if (l1 == l2) break;
}
l2 = 0;
while (l1 != l2) {
l1 = nums[l1];
l2 = nums[l2];
}
return l1;
}
