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; }
