LeetCode.42. 环形链表 II
一道很经典的链表题，要解决两个问题：
- 判断是否存在环：快慢双指针，若两个指针相遇则说明有环；找到环的入口：通过数学推导，可以发现：两个节点，分别从头结点和快慢指针相遇点开始移动，再次相遇的点就是环的入口；
数学推导：
（盗图from代码随想录）
相遇时： slow指针路程：S(slow) = x + y + n1 (y + z)fast指针路程：S(fast) = x + n2 (y + z) + y又因为：S(slow) * 2 = S(fast) ； 所以：x = (n - 1)( y + z) + z所以，从头结点到入环口恰好等于从相遇点到入环扣的距离加上（n-1）倍环长；So两个节点，分别从头结点和快慢指针相遇点开始移动，再次相遇的点就是环的入口；
Java：
public class Solution {
public ListNode detectCycle(ListNode head) {
// 双指针
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 发现环
if (slow == fast) {
//两个节点，分别从头结点和相遇点开始移动，再次相遇的点就是环的入口
ListNode index1 = head;
ListNode index2 = fast;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
复杂度分析：
时间复杂度：O(n)空间复杂度：O(1)
