力扣141.环形链表

141. 环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路一:双指针法

 1 public class Solution {
 2     public boolean hasCycle(ListNode head) {
 3         // 快慢指针
 4         // 两指针以不同的速度同时向后移动，如果在某个地方相遇了说明含有环
 5         ListNode slow = head, fast = head;
 6         while(true){
 7             if(fast == null || fast.next == null){
 8                 return false;
 9             }
10             slow = slow.next;
11             fast = fast.next.next;
12             if(slow == fast)
13                 break;
14         }
15         return true;
16     }
17 }

力扣测试时间为0ms, 空间为39.7MB

复杂度分析：

时间复杂度：我们根据慢指针所走过的路程来作为时间复杂度的估计，假设从链表头结点到入环结点的结点个数为N1, 环的结点的个数为L,前N1的结点的时间是O(N1),下面讨论慢指针在后L个结点上所花费的时间。

根据环形跑道相向的追及问题，如果两个跑步者从同一起点出发，第一次相遇肯定是速度快着比速度慢者多跑了一圈，当两人相遇时距离他们下次相遇所花费的时间是最大的（假设花费的时间为t），其他情况下距离他们的下次相遇时间都小于这个最大值，所以从现在开始到相遇，速度快者比速度慢者多跑的距离肯定小于一圈。

慢指针入环后，此时快指针已经在环上了，所以距离他们的下次相遇时间肯定小于等于t，所以从现在开始到相遇，快指针比慢指针多跑的距离肯定小于一圈，假设慢指针的速度为v,指针的速度为kv, 那么kvt - vt <= L, 所以 vt<= L/(k-1), 又因为 k = 2, 所以 vt <= L, vt刚好是慢指针在环上经过的结点个数，所以慢指针入环后最多经过 L 个结点就会被快指针追上,所以慢指针从入环到相遇所花费的时间最大为O(L),所以总的时间为O(t) <= O(N1)+O(L) = O(n)

所以时间复杂度为O(n)

空间复杂度：O(1)

思路二：哈希法

遍历链表，遍历过程中尝试把结点放入集合中，对于每个结点，如果集合中已经存在该结点，说明存在环，返回true

 1 public class Solution {
 2     public boolean hasCycle(ListNode head) {
 3        ArrayList<ListNode> list = new ArrayList<>();    // 存储结点
 4        for(ListNode node = head; node != null; node = node.next){
 5            if(list.contains(node)){ // 如果集合中已经存在该结点，说明存在环，返回true
 6                return true;
 7            }else{
 8                list.add(node);
 9            }
10        }
11        return false;
12     }
13 }

力扣测试时间为375ms, 空间为39.8MB(这个时间花费着实有点恐怖）

复杂度分析：

时间复杂度：遍历了一次链表，所以时间复杂度为O(n),虽然复杂度是O(n), 但是力扣测试时间却这么大，应该是contains()函数的花费比较大，因为contains()不是红黑树存储，所以查找效率不是很高。

空间复杂度：空间花费主要是集合中元素的个数，最大为O(n)