一.题目介绍

1.题目来源

链接：LeetCode

2.题目

给定一个链表的头节点head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始。如果pos是-1，则在该链表中没有环。 注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。 (官方的示例1图居挂了)

二.具体实现

1.实现思路

之前也遇到个是否有环的问题，而且是否有环的判断还是对数组中的元素进行遍历以后，对了元素依次比较然后判断其是否头尾相接即存在环，反正则不存在，这题借助hashset的特点就很容易实现，如果题目提到不需要额外的空间则hashset就不能使用了，那接下来看看具体的实现。

2.实现代码

1)自己的实现方式

public ListNode detectCycle(ListNode head) {
       //借助hashset
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
        //将元素添加到hashset中
            set.add(head);
            head = head.next;
            //如果添加时发现元素已存在，即首尾相接，找到了环反正则没有找到，没有存在环
            if (set.contains(head)) {
                return head;
            }
        }
        return null;
    }
复制代码

2)题友的实现方式

使用快慢指针判断是否为环形，并且将快指针重新指向头，下一次和慢指针相交就是环形开始处。

3.运行结果

三.题后思考

有时候一些题目如果借助额外的空间，比如hash这种会事半功倍，但是其实这种算是一种'投机取巧'的做法，在现有的前提是实现算法，解题的最佳方法应该是不借助额外的空间，即减小其时间复杂度。