1.问题描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
示例1
示例2
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点
示例3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示
- 链表中节点的数目范围在范围
[0, 104] 内 -105 <= Node.val <= 105pos 的值为 -1 或者链表中的一个有效索引
难度等级
中等
题目链接
2.解题思路
这道环形链表II是环形链表的升级版，在环形链表那道题的基础上，要求我们找出链表入环的第一个节点。
首先第一步，我们还是得确认它是一个环形链表，是环形链表才要考虑什么入环之说。我们可以把它依旧看成一个追及相遇问题，定义两个快慢指针来模拟两个人相互追及。
//快指针
ListNode fast = head;
//慢指针
ListNode slow = head;
如果链表真的是环形链表的话，它就会形成一个圈，那么我们的快慢指针相当于两个人从同一个入口进入一个闭环的操场在跑步。快的那个人只要时间足够，就可以比慢的那个人多跑一圈而相遇。
我们假设快指针的步频为2，慢指针步频为1，如果快指针能走到尽头，遇到null，说明不是环形链表，如果与慢指针相遇，说明是环形链表。
//快指针走两步
fast = fast.next.next;
//慢指针走一步
slow = slow.next;
//判断是否追上->有环
if(fast == slow){
......
}
证明它是一个环形链表之后，接下来我们就要来解决如何找到入环的第一个节点问题。想要解决这个问题，需要借助一点数学计算，我们一步一步来看。
我们假设入环前有x个节点，快慢指针在入环后的第y个节点相遇，相遇之后还要再走z个节点才能回到入环的第一个节点。
那么，慢指针走过的节点数为x + y，快指针走过的节点数为 x + N(y+z) + y,(N>=1)。看到这里，大家可能会有点疑惑，为什么快指针可能走很多圈，而慢指针走不完一圈呢？这是基于我们慢指针步频为1，快指针步频为2分析出来的。快指针用于比慢指针多走一个节点，我们假设它们同时从第一个交点出发的话，当慢指针绕了一圈时，快指针已经饶了两圈与它相遇了，而实际它们的出发点大概率不是入环的交点，前面还有x个环外的节点要走，所以慢指针还没走完第一个就会和快指针相遇了。
上面，我们已经分析出来，快慢指针走过的节点数，我们可以根据它们步频的关系列出这样一个等式 2 * (x + y) = x + N(y+z) + y ,我们把它化简一下可以得到 x + y = N(y + z) 。
此时这里有三个变量，x , y , z，我们重点要关注的是z，因为很直观的来看，我们如果再经过z个节点，就又可以回到入环的第一个节点了。所以我们要拿一个z出来，变换一下得到一个新的式子: x = (N-1)(y+z) + z。
从上面我们得到的式子可以看出，如果N=1，那么x=z，这种情况就是快指针走完一圈了，慢指针刚好到达入口，还没开始走。想要找到入环的第一个交点，我们只需要定义两个指针，分别从链表头，与快慢指针相遇的位置开始走一段相同的，这两个指针最终会在入环的第一个交点处相遇，这样我们就找到了入环的第一个交点了。
//从快慢指针相遇的位置出发
ListNode index1 = fast;
//从链表头出发
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
当N大于1时，情况也差不多，只是在环内的指针多走了几圈，最终还是会和从链表头开始走的指针在入环的交点处相遇，将相遇的节点返回即可。
如果不是环形链表，最后返回空就好了。
3.代码展示
/**
* 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;
//慢指针
ListNode slow = head;
//追及
while(fast != null && fast.next != null){
//快指针走两步
fast = fast.next.next;
//慢指针走一步
slow = slow.next;
//判断是否追上->有环
if(fast == slow){
//从快慢指针相遇的位置出发
ListNode index1 = fast;
//从链表头出发
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
4.总结
这道题是在是否是环形链表的基础上，多加了找到入环第一个交点的要求，要解决这个问题，用到了一点数学的计算，不过也不是很难，还是在可以接受的范围之内的，得出相关的数学表达式之后，这道题就迎刃而解了。今天这道题就啰嗦到这里，祝大家刷题愉快~