1.题目

2.思路

方法一——哈希表记录节点

思路很简单，记录一下每个节点出现的次数，如果某个节点出现了两次，代表此时有环，并且是环的入口，直接返回即可。

时间复杂度O(N)

空间复杂度O(N)

public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set<ListNode> visited = new HashSet<ListNode>();while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;}
}

方法二——快慢指针找到环 + temp指针找到环的入口

想法：首先把问题拆分成两个问题，第一个问题判断是否有环。第二个问题，如果有环的话，如何判断环的入口呢？并且保证空间复杂度为O（1）。

第一个问题很好解决。直接快慢指针就可以。

slow指针走一步

fast指针走两步

如果链表存在环，那么必然fast指针和slow指针会相遇。为什么呢？

简单的正面如下：

假如slow刚好走到环的入口，此时fast指针必然在环中的任意一个位置，此时他们之间的距离为length, 这个长度length 必然小于环的大小。

每一次，fast 都会比slow多走一步，所以下次他们之间的距离为length-1.

再下一次他们的距离为length - 2.

...

直到他们两相遇！！！

并且可以得到的是，slow不会走过一圈，他们就会相遇！因为这个距离length小于环的大小。

如果链表存在环，那么如何找到环的入口呢？（变形：如何求出环的大小？）

先说结论。此时定义一个temp指针，指向 head, 让slow 和 temp同时移动，他们相等的时候就是环的入口。

证明如下：（借用官方题解的一个图）

a : 起点到环的入口的举例为a

b：环的入口到快慢指针相遇的位置。

c：环的大小减去b的距离

首先可以得知slow指针移动的距离： a + b

然后可以得知fast指针移动的距离：a + b + n * (b + c)

然后利用fast指针速度是slow指针的两倍，所以在相同的时间下，距离也应该是两倍关系。

所以有2 *(a + b) = a + b + n * (b + c)

因为我们要计算a，所以我们想办法把a放在左边，那么化简可以得到

a = nb - b + nc

这样看不出来什么东西，所以进一步想，因为有环的大小为b + c，所以想办法凑在一起。有

a = (n - 1) * (b + c) + c

这时候可以发现，

左边的值等于一个temp指针从起点走到环的入口

右边的值相当于是slow指针先走距离c, 到达环的入口，然后再走n - 1 圈，直到两个相遇！！！！！！！

所以有结论：当快慢指针相等的时候，让slow 和 temp同时移动，他们相等的时候就是环的入口。

时间复杂度O(N)

空间复杂度O(1)

/*** 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) {// 时间O(n)// 空间O(1),这里使用的是三个指针，不占用空间ListNode slow = new ListNode(-1), fast = new ListNode(-1);slow = head;fast = head;while(fast != null){if(fast.next != null && fast.next.next != null){fast = fast.next.next;}elsereturn null;slow = slow.next;if(slow == fast){ //代表有循环// 找到环的入口ListNode temp = head;while(temp != slow){temp = temp.next;slow = slow.next;}return temp;}}return null;}
}